题意:环形跑道上有n n<=100000 个加油站  编号为1-n  第i个加油站可以加油pi加仑   从加油站i开到下一站需要qi加仑   你可以选择一个加油站作为起点 初始油箱为空   如果可以走完一圈  那么输出最小的起始站点  否则输出-1

如果   对每个加油站作为起始点进行枚举的话  那么复杂度为 n^2

其中有一个重要的思路可以优化:

比如从第一个点最为起始点   如果能走一圈 那么就成了  第一个也为最小起始点

如果 走到t点   t到t+1走不了     那么 第2个点到 第t个点作为起始点 都是一定不可行的!!

接下来就将t+1作为起始点再次尝试遍历

#include<bits/stdc++.h>
using namespace std;
#define N 100001 int vis[N];
int p[N],q[N];//p为加油 q为油耗
int n; int go(int start)
{
int oil=p[start]-q[start];
if(oil<) return start;
for(int i=(start+)%n; i!=start;i=(i+)%n )
{
oil+=p[i]-q[i];
if(oil<)return i;
}
return N;
} int solve(void)
{
int start=;
memset(vis,,sizeof vis);
vis[]=;
for(;;)
{
int e=go(start);
if(e==N)return start;
start=e+;
if(vis[start])return -;
vis[start]=;
}
} int main()
{
int cas;cin>>cas;
for(int kase=;kase<=cas;kase++)
{
cin>>n;
for(int i=;i<n;i++)scanf("%d",&p[i]);
for(int i=;i<n;i++)scanf("%d",&q[i]); int ans=solve();
printf("Case %d: ",kase);
if(ans==-)printf("Not possible\n");
else printf("Possible from station %d\n",ans+);
}
return ;
}

LRJ的代码更快更巧妙!去掉了vis数组

// UVa11093 Just Finish it up
// Rujia Liu
#include<cstdio> const int maxn = + ;
int n, p[maxn], q[maxn]; // returns s if success
// otherwise, return the station you failed to reach
// if you failed to reach the start, return -1
int go(int s) {
int fuel = p[s] - q[s];
for(int i = (s+)%n; i != s; i = (i+)%n) {
if(fuel < ) return i;
fuel += p[i] - q[i];
}
if(fuel < ) return -; // this means sum(p) < sum(q), so this case is impossible
return s; // success
} int solve() {
int start = ;
for(;;) {
int finish = go(start);
if(finish < start) return -; // wrapped around, or go(start) returns -1
if(finish == start) return start;
start = finish;
}
} int main() {
int T;
scanf("%d", &T);
for(int kase = ; kase <= T; kase++) {
scanf("%d", &n);
for(int i = ; i < n; i++) scanf("%d", &p[i]);
for(int i = ; i < n; i++) scanf("%d", &q[i]);
int ans = solve();
printf("Case %d: ", kase);
if(ans < ) printf("Not possible\n");
else printf("Possible from station %d\n", ans+);
}
return ;
}
05-27 01:30