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