https://cn.vjudge.net/problem/36467/origin

环形的一个跑道 有若干加油站 问能不能从一个加油站开始跑完一圈

如果从a跑到b，则油箱内剩余的油必定大于等于0 所以如果p跑不到p+1，就直接从p+1为起点枚举

AC代码：

#include <iostream>
#include <cstdio>
using namespace std;
int a[100010],b[100010];
int main()
{
    int kase=0,t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        int ans=0,cnt=0,p=1;
        for(int i=1;i<=n;i++)
        {
            ans+=(a[i]-b[i]);
            if(ans<0)
            {
                p=i+1;
                cnt+=ans;
                ans=0;
            }
        }
         printf("Case %d: ", ++kase);
         if(ans+cnt>=0) printf("Possible from station %d\n", p);
         else puts("Not possible");
    }
    return 0;
}
复制