题目描述 uim在公司里面当秘书，现在有n条消息要告知老板。每条消息有一个好坏度，这会影响老板的心情。告知完一条消息后，老板的心情等于之前老板的心情加上这条消息的好坏度。最开始老板的心情是0，一旦老板心情到了0以下就会勃然大怒，炒了uim的鱿鱼。
uim为了不被炒，知道了了这些消息（已经按时间的发生顺序进行了排列）的好坏度，希望研究如何不让老板发怒。
uim必须按照时间的发生顺序逐条将消息告知给老板。不过uim可以使用一种叫“倒叙”的手法，例如有n条消息，小a可以从k,k+1,k+2…n,1,2…k-1这种顺序通报。
他希望知道，有多少个k，从k开始通报到n然后从1通报到k-1可以让老板不发怒。
输入输出格式 输入格式： 第一行一个整数n(1 <= n <= 10^6)，表示有n个消息。
第二行n个整数，按时间顺序给出第i条消息的好坏度Ai(-1000 <= Ai <= 1000)
输出格式： 一行一个整数，表示可行的方案个数。
输入输出样例 输入样例#1： 4 -3 5 1 2 输出样例#1： 2 说明 样例解释
[5 1 2 -3]或[1 2 -3 5]
对于25%数据n<=1000
对于75%数据n<=10000
对于100%数据n<=10^6
P2629 好消息，坏消息 题解 最近的训练内容是单调队列，于是就找来一些题目练练手。 对于这道题，显然k有n种可能的情况，我们只要对每个k判断是否合法即可。但如果暴力枚举每一个k，时间复杂度是 的，需要考虑优化。 在考虑优化前，我们先介入一种思想——断环为链，这样可以方便处理对于每一个k的情况。说通俗点就是在n后面再接上1–(n-1)的值，所以数组要开双倍长度。 以样例为例：-3 5 1 2，我们将其断环为链后可以得到这样的一组数据：-3 5 1 2 -3 5 1，并设其下标为1–7。当k=1时，需要判断的就是下标1–4；当k=2时，就是下标2–5；当k=3时，就是下标3–6；当k=4时，就是下标4–7（显然k不会等于5）。 断环为链后，题目要求就变为了：对于每一个合法的k，都要满足k–(n+k-1)中，到任意一点的和都是非负的。熟悉前缀和的人应该知道，如果用s[i]表示1–i的所有数的和，那么s[j]-s[i-1]就是i–j所有数的和。所以用前缀和预处理后，s[i]-s[k-1]就是k–i(k<=i<=n+k-1)的和了，我们只要判断这个和是否为负即可。 既然这么说，那么是否要判断k–n+k-1中每一个数的和呢？当然不是，因为其中如果只要有一点的和是负的，那么这个k就是不合法的了，所以我们只需要判断一次——判断最小的si减去s[k-1]是否为负。 那么这题的思路就很明确了，先对输入数据断环为链，然后在链上进行前缀和的预处理，最后，对于每一个k+n-1，我们用单调队列维护k–k+n-1的最小值，并将其减去s[k-1]判断是否合法。 代码如下： #include #include using namespace std; int n,head=1,tail,ans; long long a[2000001],s[2000001],q[2000001]; int main() { scanf("%d",&n); for(register int i=1;i<=n;i+=1) scanf("%lld",&a[i]); for(register int i=1;i<=n-1;i+=1) a[i+n]=a[i]; for(register int i=1;i<=2n-1;i+=1) s[i]=s[i-1]+a[i]; for(register int i=1;i<=2n-1;i+=1) { while(head<=tail&&max(i-n+1,1)>q[head])head++; while(head<=tail&&s[i]<=s[q[tail]])tail–; q[++tail]=i; if(i-n+1>0&&s[q[head]]-s[i-n]>=0)ans++; } printf("%d\n",ans); return 0; }
