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;
}