一、题意

环形跑道上有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跳出,这样代码会比较好写。