UVa 11093 环道（Just Finish it）

问题描述：沿环形道路设置有n个加气站，在第i号加气站最多能容纳pi加仑的汽油。经过第i号加气站前往下一个相邻的加气站时会消耗qi加仑的汽油。你可以选择任何一个加气站作为出发点，并在出发前可以在该处补充所需的燃料（出发时无需携带任何汽油）。你需要确定一个合适的出发点，并最终能返回到选定的出发点（假设油箱容量没有上限）。如果无法完成整个行程，则输出Not possible；否则则需输出所有可行方案中编号最小的那个起始点

分析：贪心算法在资源分配问题中表现出色。假设你能够从位置i移动到位置j的情况下，在到达位置j时也必定能够继续前进至更远的位置吗？这个问题的答案是否定的。进一步思考可知：当无法到达某个特定的位置时，则表明该特定的位置之前的某个区间内存在某种限制条件——即其储存能力不足以支持下一步行程。依次类推下去，则可以得出结论：这样的起点不可能存在——因为一旦能够前进步伐就必须处于节省资源的状态。

好，有了这个想法的话，就可以在O（n）的时间解决问题。

代码：

    #include<bits/stdc++.h>
    #define LL long long
    #define ms(s) memset(s, 0, sizeof(s))
    using namespace std;
    const int maxn = 1e5