贪心+后缀和，CF 1903C - Theofanis‘ Nightmare

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

1903C - Theofanis' Nightmare

---

二、解题报告

1、思路分析

我们任意一种分组其实都是若干个后缀和相加

比如我们分成了三组，第一组的数被加了一次，第二组的数被加了两次，第三组的数被加了三次

加入nums[0, 3]为第一组，nums[4, 5]为第二组，nums[6, 7]为第三组，后缀和acc[i]代表从i开始的后缀和

那么相当于acc[0] + acc[4] + acc[6]

那我们预处理后缀和只要大于0就加就行了

为了保证合法性，必须加一下整个数组和

2、复杂度

时间复杂度： O(N)空间复杂度：O(N)

3、代码详解

 ​

import heapq
import sys
from collections import Counter
from collections import deque
from itertools import accumulateinput = lambda: sys.stdin.readline().strip()
MII = lambda: map(int, input().split())
LMI = lambda: list(map(int, input().split()))
I = lambda: int(input())
fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
P = 998244353def main():n = I()a = LMI()acc = list(accumulate(a[::-1]))res = acc[-1]for i in range(n - 2, -1, -1):if acc[i] > 0:res += acc[i]print(res)if __name__ == '__main__':T = I()for _ in range(T):main();