2017 ACM/ICPC Asia Regional Shenyang Online card

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=6205

题目大意：给出两个长度为n的序列A，B，从1开始依次加Ai，减Bi，分数为第一次为当前和为负数的位置以前的Ai之和（左闭右开区间）。

同时有一种操作可以把当前的A1，B1移动到序列最后，注意序列A的各个元素之和等于B的各个元素之和。

问取得最大分数时，至少应该操作多少次。

恩，先自我反思一下，比赛时又nc了，写了个什么单调队列什么的，又花时间还容易错，虽然人品好一发过了，但是还是掩饰不了我的菜QAQ

其实把前缀和处理一下，找到前缀和最小的位置，就是最小操作次数。

因为如果把前缀和记录下来会是一个循环的折线图，所以从最低点开始往后累加Ai-Bi的话，肯定不会比当前值更低，所以就可以分数为序列A的所有元素之和，为最大值。

代码：

#include <bits/stdc++.h>

using namespace std;
inline void read(int &x){
    char ch;
    bool flag=false;
    for (ch=getchar();!isdigit(ch);ch=getchar())if (ch=='-') flag=true;
    for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());
    x=flag?-x:x;
}

inline void read(long long &x){
    char ch;
    bool flag=false;
    for (ch=getchar();!isdigit(ch);ch=getchar())if (ch=='-') flag=true;
    for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());
    x=flag?-x:x;
}


inline void write(int x){
    static const int maxlen=100;
    static char s[maxlen];
        if (x<0) {   putchar('-'); x=-x;}
    if(!x){ putchar('0'); return; }
    int len=0; for(;x;x/=10) s[len++]=x % 10+'0';
    for(int i=len-1;i>=0;--i) putchar(s[i]);
}

int const maxn=1000010;
int sum_a[maxn],sum[maxn];
int n;
int main(){
    while (scanf("%d",&n)!=EOF)
        {
            for (int i=1;i<=n;i++)
            {
                int x;
                read(x);
                sum_a[i]=sum_a[i-1]+x;
            }
            for (int i=1;i<=n;i++)
            {
                int x;
                read(x);
                sum[i]=sum[i-1]+sum_a[i]-sum_a[i-1]-x;
            }
            int Min=sum[0];
            int Mini=0;
            for (int i=1;i<=n;i++)
                if ( sum[i]<Min)
                    {
                        Min=sum[i];
                        Mini=i;
                    }
            printf("%d\n",Mini);
        }
    return 0;
}