https://vjudge.net/problem/UVA-11093

题意:环形跑道上有n个加油站,编号为1~n。第i个加油站可以加油pi加仑,从加油站i开到下一站需要qi加仑汽油。输出最小的起点,使得可以走完一圈后回到起点。

思路:直接枚举。注意剪枝就可以了,如从1号加油站出发,开到加油站p前没油了,那么2,3,4...p-1肯定不是解。

 #include<iostream>
using namespace std; const int maxn = + ;
int n;
int ans;
int p[maxn];
int q[maxn]; bool solve()
{
int pas;
int ok = ;
for (int i = ; i < n; i++)
{
pas = ;
for (int j = ; j <= n; j++)
{
int t = (i + j) % (n + );
pas += p[t];
pas -= q[t];
if (pas < )
{
if (t>=i) { i = t; break; } //t还没有作为过起点
else return false; //t已经作为过起点
}
if (j == n && pas >= ) ok = ;
}
if (ok) { ans = i; return true; }
}
return false;
} int main()
{
//freopen("D:\\txt.txt", "r", stdin);
int t, kase = ;
cin >> t;
while (t--)
{
cin >> n;
for (int i = ; i < n; i++)
cin >> p[i];
for (int i = ; i < n; i++)
cin >> q[i];
if (solve()) cout << "Case " << ++kase << ": Possible from station " << ans+ << endl;
else cout << "Case " << ++kase << ": Not possible" << endl;
}
return ;
}
05-08 08:27