加拿大旅游计算机竞赛，优化问题

Question

问题4来自CCC 2019

问题描述 你计划去参观N个旅游景点。景点编号从1到N 必须按此顺序访问。你每天最多可以参观K个景点，并计划旅行 以尽可能少的天数。 在这些限制条件下，你想找到一个在景点之间有很好平衡的时间表 每天访问。准确地说，我们分配了一个分数 给一个时间表，每天 给出的分数等于当天参观的所有景点的最高分数。最后 每一天都要加总，得出日程的总分。最大可能总数是多少 用最少的时间安排？ 输入规范 第一行包含两个空格分隔的整数N和K（1≤K≤N≤10^6） ). 下一行包含N个空格分隔的整数ai（1≤ai≤10^9） ). 15分中有3分，2K≥N。 对于15个可用标记中的另外3个，K≤100和N≤10^5 . 输出规格 输出单个整数，最大可能的总分。 样本输入 5 3个 2 5 7 1 4 样本输入输出 12 样本输入输出说明 我们需要至少两天的时间游览所有景点，因为我们不能游览所有的景点 有一天。 第一天参观前两个景点得5分，最后三个景点得5分 第二天得7分，总分12分。 第一天游览三个景点，第二天游览两个景点，这是唯一可以 在尽可能短的天数内就诊，总分为7+4=11。在

我的方法 使用递归遍历初始吸引力，然后在第二天发送部分，并在每个递归中找到最高分数

def scores(things, att, days):
    minper = attractions(att,row1[1])

    if att <= 0:
        return 0, False
    if days > minday:
        return 0, True
    else:
        maxscore = 0
        for y in range(minper,row1[1]+1):
            score, more = scores(things[y:],att-y,days+ 1)
            if not(more):
                score += max(things[:y+1])
            if score >= maxscore:
                maxscore = score
        return maxscore, False

def attractions(attr,maxper):
    if (attr % maxper) == 0 and attr > 0:
        return maxper
    return (attr % maxper)

row1=(input()).split(" ")
places=(input()).split(" ")

for x in range(len(row1)):
    row1[x] = int(row1[x])

for x in range(len(places)):
    places[x] = int(places[x])

if (row1[0]/row1[1])%1 == 0:
    minday = int(row1[0]/row1[1])

else:
    minday =(row1[0]//row1[1]) + 1

if minday !=1:
    maxscore = 0
    for x in range(attractions(row1[0],row1[1]),row1[1]+1):
        score, more = scores(places[x:],row1[0]-x,1)
        if not(more):
            score += max(places[:x])
        if score >= maxscore:
            maxscore = score
    print(maxscore)
else:
    print(max(places))

这些问题的测试用例包括N为1000000，K为999999的数字，这意味着两天（最短天数）每天可能的出行次数为1999999999998。。。99999 8,2 999999,1，这对于这种方法来说太长了，还有另一种情况，例如，N=51，K=10，所以它可以是10,10,10,10,1或10,1,10,10,10,10，10，10或者它也可以是9,9,9,9,9,9,6等等，但是它覆盖了所有的数字排列，这些数字加起来就是最小天数。如何更好地优化这一点，或者有更好的方法在1秒内完成。在

Answer 1

以下是我的建议（一种天真的方法）：

• 最短天数（D）为（N-1）//K+1
• 如果N是D的倍数，那么你只有一种方法来组织D天的假期。在
• 否则，从第一天到第1天参观K个景点开始，最后一天参观其余景点（R）=N-K*（D-1）
• 把这个放在一个基本的数组中，位置代表一天
• 然后，你只需要在第一天分配K-R景点，用最后一天交换一些景点。在
• 使用暴力方法，您将从1循环到K-R，以获取要交换的景点数量。在
• 在这个循环中，您需要将第一个D-1天中的S天的组合扩展为同一天的可能重复。（Python的itertools模块有一个函数可以做到这一点：组合使用\u和\u替换）
• 对于这些组合中的每一个，从基数组的副本中交换相应的吸引力计数，计算并跟踪该假期计划的最大评分总和。在
• 时间应为D*[1+Cr（D-1,2）+Cr（D-1,3）+。。。Cr（D-1，S）]，其中Cr（n，r）是n中r与重复的组合：（r+n-1）！/（r！（n-1）！）在

特殊情况：2K>；N（最少天数=2）

当只有两个假期时，考虑到这两天有一个共同的重叠点，在任何一天都可以看到景点，算法可以大大简化。此外，还有第一天必须参观的主要景点和第二天必须参观的尾随景点。因此，我们正在寻找领先、落后和普通群体之间的前2大吸引力。领头组和尾随组最多只能有一个“顶级吸引力”，普通组最多可以有两个。在

因此，只有4种方式可以将前两大景点分布在三个组别之间：

[ -lead -][ -common -][ -tail -]
    X             X                    
                  X X             
                  X            X
    X                          X

取max（lead）、max（tail）和common的top2之间的前2个值，我们将得到最好的组合，如这里用4个模拟值所示。在

^{pr2}$

• 确定最小就诊次数（MV）=N%K
• 第一次和最后一次MV访问必须是第一天和第二天的一部分（分别）
• 这将被确定为主要访问（LV）和跟踪访问（TV）
• 从LV+1中找出普通访问（CV）的前两个分数。。。包括N-TV（TopCommon1、TopCommon2）
• 找到前导和尾随访问的最吸引人的地方（LV->；LT，TopLead->；TopTail）
• 找到TopLead、TopCommon1、TopCommon2、TopTail中的前2名
• 把它们加起来就得到这次旅行的总分

其他情况下的更好算法

为了改进上述暴力行为，我们可以计算每一个景点在一天中的第一个景点的部分行程分数。这可以从最后一个逐步计算到第一个。那么第一个景点的旅行分数就是答案。在

• 从最后一个景点开始，倒推到第一个景点（AN=景点编号）
• 确定还有多少景点（包括这一个）：（RA）=N-AN+1
• 确定RA景点的天数（RD）=（RA-1）/K+1
• 确定当天需要完成的最少就诊次数（MV）=RA-K*（RD-1）
• 当天可能的访问量从MV到K
• 对于此范围内的每次访问计数（VC），计算该范围内景点的最大访问分数（MS）（当前日期…+VC）。在
• 下一个景点将是第二天的第一个
• 我们已经计算了当天的吸引量和总访问量

注意，可以通过执行边缘情况的impler计算，例如“最小访问”范围内的第一次和最后一次访问。我认为这只在K非常大（但不大于N/2）且N mod K接近K的情况下才有意义