题目链接：
UVALive 6087 Fuel Stops
题意:
有n个城市，要做一次环游，每到一个城市可以增加一定的油量同时也会消耗一定的油量，要保证环游过程中到每个城市的油量非负，选择起点城市有多少个？保证有解。( n≤105 )
分析：
可以把每个城市的增加油量和消耗油量先相减，那么其实就是求数环上任意前缀和都非负的点有多少个？
我们先从第一个城市开始，找到第一个满足条件（从当前位置到 n?1 的前缀和都是非负）的城市 st ，用 pre[]表示前缀和 ,对于从 0到st 之间的任意城市 i 都是不满足条件的，因为到达
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 100010;int n, cases = 0, total, st;
int data[MAX_N], pre[MAX_N], sum[MAX_N], suf[MAX_N], ans[MAX_N], Min[MAX_N];int main()
{while(~scanf("%d", &n) && n) {for(int i = 0; i < n; ++i) scanf("%d", &data[i]);st = total = 0;for(int i = 0; i < n; ++i) {int tmp;scanf("%d", &tmp);data[i] -= tmp;sum[i] = sum[i - 1] + data[i];if(i == 1) Min[1] = data[1];else Min[i] = min(Min[i - 1], sum[i]);}pre[0] = data[0];for(int i = 1; i < n; ++i) {if(pre[i - 1] < 0) {pre[i - 1] = 0;st = i;}pre[i] = pre[i - 1] + data[i];}ans[total++] = st;suf[n - 1] = pre[n - 1];for(int i = n - 2; i > st; --i) {suf[i] = min(suf[i + 1], pre[i]);}for(int i = st + 1; i < n; ++i) {if(suf[i] - pre[i - 1] >= 0 && Min[i - 1] + pre[n - 1] - pre[i - 1] >= 0) ans[total++] = i;}printf("Case %d:", ++cases);for(int i = 0; i < total; ++i) {printf(" %d", ans[i] + 1);}printf("\n");}return 0;
}