题意：给出n个加油站，任意选择一个起点，看是否能够绕一圈又回到这个起点
看的紫书： 假设从第一个点出发最多能够到达p,那么从1到p的点就一定都不是起点了
比如说：从1出发，最多能够到10，都不能够回到起点，这种情况下，它到达2还剩下有汽油，
如果从2出发，汽油量为0，能够去到的路程就更短了，所以不可能
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 using namespace std; 12 13 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) 14 15 typedef long long LL; 16 const int INF = (1<<30)-1; 17 const int mod=1000000007; 18 const int maxn=1000005; 19 20 int p[maxn],q[maxn]; 21 22 int main(){ 23 int T; 24 scanf("%d",&T); 25 int kase=0; 26 while(T--){ 27 int n; 28 cin>>n; 29 for(int i=0;i<n;i++) cin>>p[i]; 30 for(int i=0;i<n;i++) cin>>q[i]; 31 32 int pos; 33 int i=0,flag; 34 while(i<n){ 35 int ans=0; 36 flag=1; 37 38 for(int j=0;j<n;j++){ 39 pos=(j+i)%n; 40 41 ans+=p[pos]; 42 ans-=q[pos]; 43 if(ans<0){ 44 flag=0; 45 break; 46 } 47 } 48 49 if(flag) break; 50 if(pos<i) {//重复了，说明已经枚举完一圈可能的，都还是没有找到可能的起点，跳出 51 flag=0;break; 52 } 53 i=pos+1; 54 } 55 56 printf("Case %d: ",++kase); 57 if(flag) printf("Possible from station %d ",i+1); 58 else printf("Not possible "); 59 } 60 return 0; 61 }