题目链接：http://hihocoder.com/problemset/problem/1831
题目大意：
世界各地的一个圆圈上有n个城市，它们按照圆圈上的顺序从1到n编号。当你到达这个城市会得到ai块钱，从这个城市去另外的城市要花费bi块钱，这个游戏的目标是选择一个城市作为起点，一开始你有c美元，然后沿着圆圈去一次访问整个城市，最后回到起点。在旅途中，你的钱必须不低于零。
这里有一个问题：要完成这次旅行，您会选择哪个城市作为开始城市？
如果有多个答案，请输出编号最小的答案。
如果没有答案， 输出-1

输入的第一行是一个整数T（T ≤100），的测试案例数量。
对于每一个测试的情况下，第一行包含两个整数N和C（1≤N ≤10^6， 0≤ C≤10^9）。
第二行包含N个整数ai(- 10^9 ≤ ai ≤10^9)，
第三行包含N个整数bi…bn（0≤ bn ≤10^9）。

保证所有测试用例中n的总和小于10^6

思考：

因为到一个城市先得到钱，所以经过一个城市得到的钱为a[i]-b[i];
图中ai=a[i]-b[i];

首先求前缀和，判断s[n]+m>=0，如果成立则可以访问全部城市。
这时枚举起始城市，如果以1为开始城市，则是s[i]+m,…,s[n]+m都要>=0。
如果以2为开始城市，则以2为起始城市的n个城市的前缀和都要>=0。
…
以此类推

如果每枚举一个起点，求一次前缀和，复杂度为O（T*n^n），肯定会T。

那么我们可以动态维护前缀和。
假如以2为起点时，除a1的前缀和，其他的前缀和都-=a1。而s[1]=(a[1]-b[1])+s[n-1];
假如以3为起点时，除a2的前缀和，其他的前缀和都在以2为起点的基础上-=a2。而s[2]=(a[2]-b[2])+s[1];
…
以此类推

那么所有的-=可以用s3记录下来，那么每次只要维护s[i-1]就行了。
用multiset存储前缀和，那么每次找min前缀和的复杂度为log n。
整体的复杂度为O（T* n*log n）

思考：当时T了很多次，后来发现是数组开小了。。。。。，话说怎么不是MLE。。。。
因为T了很多次，当时以为O（T* n*log n）的f’z’d过不了，还想到一种O（T *n）的思路，不过没有验证过是否正确。

记录第一次的前缀和的最小值S(min)，和下标j，在每次枚举起点i时，除S[i-1]外，所有的前缀和都减去相同的数，所以S(min)=min( S(min), S[i-1] )

如果S[min]的下标为j, 则所以的枚举i<=j都没使S[min]-s3+m>=0, 则起点为j+1(没有证明)

刚才再看了当时的代码，发现维护前缀和的地方，维护的是S[i]的前缀和，竟然AC。。。。。数据太水？？？

#include<bits/stdc++.h>
using namespace std;

int a[1000005];
int b[1000005];
long long s[1000005];


int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        multiset<long long> st;
        int n, m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=0;i<n;i++)
        {
            scanf("%d",&b[i]);
        }
        s[0]=a[0]-b[0];
        long long s1=s[0];
        for(int i=0;i<n;i++)
        {
            s[i]=s[i-1]+a[i]-b[i];//前缀和
            st.insert(s[i]);
        }
        s1=s[n-1]+m;
        if(s1>=0)//如果成立则可以访问全部城市。
        {
            long long s2=*st.begin();//前缀和的最小值
            long long s3=0;
            if(s2+m>=0)              //第一个城市
            {
                printf("1\n");
            }
            else
            {
                for(int i=1;i<n;i++)
                {
                    s3+=(a[i-1]-b[i-1]);//记录s3
                    st.erase(st.find(s[i-1]));
                    if(i==1)
                    {
                        s[0]=(a[0]-b[0])+s[n-1];//i="2"特殊维护
                        st.insert(s[0]);
                    }
                    else
                    {
                        s[i-1]=(a[i-1]-b[i-1])+s[i-2];//维护前缀和
                        st.insert(s[i-1]);
                        /*
                        写成
                        s[i]=(a[i]-b[i])+s[i-1];
                        st.insert(s[i]);
                        也能AC
                        数据比较水？？？
                        */
                    }

                    s2=*st.begin();
                    if(s2+m>=s3)//判断是否满足条件
                    {
                        printf("%d\n",i+1);
                        break;
                    }
                }
            }
        }
        else
            printf("-1\n");
    }

    return 0;
}