C. Zero-Sum Prefixes Codeforces Round #833 (Div. 2)（前缀和+贪心）_财经资讯

C. Zero-Sum Prefixes Codeforces Round #833 (Div. 2)（前缀和+贪心）

创始人

2024-03-03 21:20:57

0次

传送门

题意：

给你一个长度为n的数组，里面包含a1,a2,a3...an n个元素，

当 a_i=0 的时候，你可以将 a_i 变成任意数字，

问你经过任意次操作后对于 1<=i<=n ，它的前i项和为0的个数是最大是多少？

思路：

假设数组一个0都没有的话：那么结果就是前缀和为0的个数。

如果只有一个0的话：那么因为改变0的值并不会改变他前面的元素的前缀和，所以对于0前面的元素res1为前半部分前缀和为0的个数：

对于后半部分因为0可以改变成任意数字，那么可以将它变成0（包括0）之后的前缀和出现次数最多的的元素的负这样可以产生出最多的前缀和为0的值res2。

最后结果就是 res1+res2

如果有两个0的话，前半部分同理依旧是res1；对于两个0中间的情况，因为第一个0改变值产生的影响对后面的元素的值的改变是一样的，那么就是说无论第一个0怎么改变，都不会影响第二个0的最优数量。那么就是从第一个0（包括）到第二个0（不包括）之间的前缀和出现次数最多的结果res2，之后再加上最后一个0到末尾的前缀和出现次数最多的结果res3， res1+res2+res3 就是当前情况的结果。

那么综合分析：对于还没有出现0的区域，这部分的答案就是前缀和为0的数量，之后每次从第一个0开始，到第二个0，找出出现元素次数最多的数量并加上，直到最后一个0到n的（也可以额外加个0在n+1的位置）结果总和加起来就是最优的情况。

/***　　┏┓　　　┏┓+ +*　┏┛┻━━━┛┻┓ + +*　┃　　　　　　　┃*　┃　　　━　　　┃ ++ + + +*  ████━████+*  ◥██◤　◥██◤ +*　┃　　　┻　　　┃*　┃　　　　　　　┃ + +*　┗━┓　　　┏━┛*　　　┃　　　┃ + + + +Code is far away from 　*　　　┃　　　┃ + bug with the animal protecting*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　*　　　┃ 　	　　　 ┣┓*　　  ┃ 　　　　　 　┏┛*　    ┗┓┓┏━┳┓┏┛ + + + +*　　　　┃┫┫　┃┫┫*　　　　┗┻┛　┗┻┛+ + + +*/#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define sc_int(x) scanf("%d", &x)
#define sc_ll(x) scanf("%lld", &x)
#define pr_ll(x) printf("%lld", x)
#define pr_ll_n(x) printf("%lld\n", x)
#define pr_int_n(x) printf("%d\n", x)
#define ll long long
using namespace std;const int N = 1000000 + 100;
int n, m, h;
ll s[N];
ll cnt[N];
map q;int main()
{int t;sc_int(t);while (t--){cin >> n;int time = 0;for (int i = 1; i <= n; i++){cin >> s[i];if (s[i] == 0)cnt[++time] = i;s[i] += s[i - 1];}cnt[++time] = n + 1;int res = 0;for (int i = 1; i < cnt[1]; i++)if (!s[i])res++;for (int i = 1; i < time; i++){q.clear();int ma = 0;for (int j = cnt[i]; j < cnt[i + 1]; j++){q[s[j]]++;ma = max(ma, q[s[j]]);}res += ma;}cout << res << endl;}return 0;
}

上一篇：1.8 打好shell基础

下一篇：沂水地下大峡谷（沂水地下大峡谷门票多少钱）沂水地下大峡谷沂水地下大峡谷值不值得去

C. Zero-Sum Prefixes Codeforces Round #833 (Div. 2)（前缀和+贪心）

相关内容

热门资讯