HDU 4193————Non-negative Partial Sums

xiaoxiao2021-02-28  129

题目描述:

You are given a sequence of n numbers a 0,..., a n-1. A cyclic shift by k positions (0<=k<=n-1) results in the following sequence: a k a k+1,..., a n-1, a 0, a 1,..., ak-1. How many of the n cyclic shifts satisfy the condition that the sum of the fi rst i numbers is greater than or equal to zero for all i with 1<=i<=n?

题意,要求是序列中的任意i满足这个i的前缀和>=0,每次操作将第一个数丢到最后,求所有这样操作能生成的序列中满足要求的有多少个;

输入,n表示n个数,范围为10的6次方,接下来n个数,n为0时输入结束;

输出:满足要求的序列数目ans;

样例:

input:

3 2 2 1 3 -1 1 1 1 -1 0 output:

3 2 0 又是一个单调队列的应用,先求一个前缀和,然后去维护一个单调增队列,这样保证该队列队首元素为该序列中最小的前缀和,如果最小值都大于等于0的话,该序列就肯定满足要求了,入队的时候注意先将不在这种情况之内的队首元素先弹出,同时去维护一个sum值来储存当前已经丢到序列尾的元素的和,因为要维护队列的单调性,所以每次入队的时候,应该加上这个sum值,然后计算时再减去就可以了。

AC代码:

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<stack> #include<queue> #include<algorithm> using namespace std; const int MAXM=1001000; struct node { int sum; int pos; }; int n; struct node a[2*MAXM]; int b[2*MAXM]; int main() { while(scanf("%d",&n)!=EOF) { memset(a,0,sizeof(a)); if (n==0) break; for (int i=1;i<=n;i++) { int x; scanf("%d",&x); b[i]=x; a[i].sum=a[i-1].sum+x; a[i].pos=i; } int ans=0; deque<node > q1; for (int i=1;i<=n;i++) { while(!q1.empty()&&a[i].sum<=q1.back().sum) q1.pop_back(); q1.push_back(a[i]); } int sum=0; for (int i=1;i<=n;i++) { while(!q1.empty()&&q1.front().pos<i) q1.pop_front(); if (q1.front().sum-sum>=0) ans++; sum+=b[i]; node t; t.pos=i+n; t.sum=a[n].sum+sum; while(!q1.empty()&&t.sum<=q1.back().sum) q1.pop_back(); q1.push_back(t); } printf("%d\n",ans); } return 0; }

转载请注明原文地址: https://www.6miu.com/read-18464.html

最新回复(0)