UVa 11093 环形跑道（模拟）

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 ;

 }