从第一个加油站开始枚举起点，如果到第i个加油站油量不够的话，那么1~i个加油站都不可能是起点。
将第i+1个加油站作为起点继续枚举。
比如说，第一个加油站开始最多跑到第5个加油站，那么第二个加油站不可能是起点。
因为第一个作为起点的话，到达第二个加油站油箱可能还有剩余，这样都跑不完一圈，所以从第二个站开始跑也就不可能跑完一圈。
#include <cstdio> const int maxn = + ;
int p[maxn * ], q[maxn * ]; int main()
{
freopen("in.txt", "r", stdin); int T; scanf("%d", &T);
for(int kase = ; kase <= T; kase++)
{
printf("Case %d: ", kase); int n; scanf("%d", &n);
for(int i = ; i < n; i++) { scanf("%d", &p[i]); p[i+n] = p[i]; }
for(int i = ; i < n; i++) { scanf("%d", &q[i]); q[i+n] = q[i]; } bool flag = false;
int cur = , pos = -, cnt = ;
for(int i = ; i < n;)
{
int cur = ;
int j = i;
while(j < i + n && cur + p[j] >= q[j])
{
cur += p[j] - q[j];
j++;
}
if(j == i + n) { pos = i; break; }
i = j + ;
} if(pos >= ) printf("Possible from station %d\n", pos + );
else puts("Not possible");
} return ;
}
代码君