Uva 11093 关于在加油站加油就是为了能跑到下一个加油站加油的这件事

一、题意

环形跑道上有n个加油站（n<=100000），编号1-n，第i个加油站可以加油p[i]加仑，从它开到下一个加油站需要q[i]加仑，要求你选择一个加油站作为起点，然后跑一圈回到起点，要求作为起点的加油站编号尽可能小。
无解则输出 Not Possible。有解则输出起点的加油站编号。

二、解析

根据贪心的思想，我们总是从小编号的加油站开始尝试，即从1号加油站开始。若它跑不到x号加油站，则说明把2....x-1号加油站作为起点也一定跑不到x号加油站，因此下一个就尝试从x号加油站开始作为起点进行尝试，以此类推，直到可以跑完一圈或者发现所有加油站作为起点都不能跑完一圈（即枚举的起点变小）为止。
时间复杂度为O(n)。

三、代码

#include <iostream>
using namespace std;
const int maxn = 100000 + 5;
int kase, n, p[maxn], q[maxn];

int main() {
    cin >> kase;
    for(int K = 1; K <= kase; K ++) {
        cin >> n;
        for(int i = 0; i < n; i ++) cin >> p[i];
        for(int i = 0; i < n; i ++) cin >> q[i];
        int start = 0, ok = 0;
        while(!ok) {
            int cnt = 0, petrol = 0, prev_start = start;
            for(int i = start; ; i = (i + 1) % n) {
                petrol += p[i], cnt ++;
                if(cnt == n + 1) {  // 跑完了一整圈回到了起点
                    ok = 1;
                    break;
                }
                if(petrol >= q[i]) petrol -= q[i];
                else {  // 跑没油了
                    start = i + 1;
                    break;
                }
            }
            if(start <= prev_start) break;  // 起点变小了，说明枚举完了
        }
        cout << "Case " << K << ": ";
        if(!ok) cout << "Not possible" << endl;
        else cout << "Possible from station " << start + 1 << endl;
    }
}

四、归纳

• 这种需要小技巧的题目还是需要自己思考，积累经验。
• 有时循环比较难写的可以先写个死循环，然后逐个思考跳出循环的条件语句，然后通过break跳出，这样代码会比较好写。