UVa 11093 环形跑道（模拟）

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

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

 1 #include<iostream> 
 2 using namespace std;
 3 
 4 const int maxn = 100001 + 5;
 5 int n;
 6 int ans;
 7 int p[maxn];
 8 int q[maxn];
 9 
10 bool solve()
11 {
12     int pas;
13     int ok = 0;
14     for (int i = 0; i < n; i++)
15     {
16         pas = 0;
17         for (int j = 0; j <= n; j++)
18         {
19             int t = (i + j) % (n + 1);
20             pas += p[t];
21             pas -= q[t];
22             if (pas < 0)
23             {
24                 if (t>=i)  { i = t; break; }  //t还没有作为过起点
25                 else  return false;   //t已经作为过起点
26             }
27             if (j == n && pas >= 0)  ok = 1;
28         }
29         if (ok)  { ans = i; return true; }
30     }
31     return false;
32 }
33 
34 int main()
35 {
36     //freopen("D:\txt.txt", "r", stdin);
37     int t, kase = 0;
38     cin >> t;
39     while (t--)
40     {
41         cin >> n;
42         for (int i = 0; i < n; i++)
43             cin >> p[i];
44         for (int i = 0; i < n; i++)
45             cin >> q[i];
46         if (solve())   cout << "Case " << ++kase << ": Possible from station " << ans+1 << endl;
47         else  cout << "Case " << ++kase << ": Not possible" << endl;
48     }
49     return 0;
50 }