Codeforces 1358D - The Best Vac

日常一道算法题。

翻译

最好的假期

你喜欢一个人很久了，直到今天才知道她在哪。

你立刻请了一个长假去找她。你会在她那待 x 天。

她那使用特殊的日历，每年有 n 个月，第 i 个月有 d[i] 天。每个月的日期是 1 到 d[i]，并且没有闰年。

她的心情随着日期的变化而变化，你会在 d[i] 天获得 d[i] 个拥抱。

你想知道，最多可以获得多少拥抱。

请注意，你旅行的开始日期与结束日期不一定在同一天。

输入格式

第一行输入 n x 用空格分开。

第二行输入 n 个整数，用空格分隔。

可以保证 x 小于等于 d 的和。

输出格式

输出一个整数，可以获得最大的拥抱数量。

分析

数据量为 10^5，时间复杂度应该为 O(n)。

预处理计算出，当前 index 的支持的最大的天数与日期总和。思路为用 left 和 right 指针的滚动计算。

然后计算每个月份作为截止日期的总数。

如果问为啥要用月份最后一天为截止日期，你猜^-

代码(Python3)

# https://codeforces.com/contest/1358/problem/D
 
import sys
import os
import heapq
import math
 
try:
    path = "./file/input.txt"
    if os.path.exists(path):
        sys.stdin = open(path, 'r')
    # sys.stdout = open(r"./file/output.txt", 'w')
except:
    pass
 
t = 1
 
def printd(value):
    # print(value)
    pass
 
def case():
    arr = list(map(int, input().split(" ")))
    n, x = arr[0], arr[1]
    arr = list(map(int, input().split(" ")))

    arr = arr * 2
    result = [0] * len(arr)
    total = [0] * len(arr)
    left = 0
    right = 0
    sum = arr[0]
    result[0] = arr[0]
    total[0] += int((1 + arr[0]) * arr[0] / 2)

    while right < n * 2:
        right += 1
        if right >= n * 2:
            break

        total[right] = total[right - 1]
        sum += arr[right]
        result[right] = sum
        total[right] += int((1 + arr[right]) * arr[right] / 2)

        while left < right and sum - arr[left] > x:
            sum -= arr[left]
            total[right] -= int((1 + arr[left]) * arr[left] / 2)
            result[right] = sum
            left += 1
    
    answer = 0
    for index in range(n * 2):
        if result[index] >= x:
            diff = result[index] - x
            value = total[index] - int((1 + diff) * diff / 2) 
            answer = max(answer, value)
    
    print(answer)

for _ in range(t):
    case()

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.06.11 长春