【例題 8-13 UVA - 11093】Just Finish it up

【鏈接】 我是鏈接,點我呀:)
【題意】

在這里輸入題意

【題解】

尺取法。
假設現在取[l..r]這一段。
然后發現累加的和小于0了。
那么方法只能是不走l..l+1這一段了
即delta遞減(p[l]-q[l]);
直到delta>=0為止。
某個時刻如果發現r+1==l 或者l==1且r==n
則合法。
如果發現l大于n了.則返回無解

【代碼】

#include <bits/stdc++.h>
#define ll long long
using namespace std;const int N = 1e5;int n;
ll p[N+10],q[N+10];int ok(){ll now = p[1]-q[1];int l = 1,r = 1;while (1){while (now <0){now-=p[l]-q[l];l++;if (l==n+1) return -1;}r++;if (r>n) r = 1;now+=p[r]-q[r];if ((r==l-1 ||(l==1 && r==n) )&& now >=0) return l;}return -1;
}int main(){int T;cin >> T;int kase = 0;while (T--){cin >> n;for (int i = 1;i <= n;i++) cin >> p[i];for (int i = 1;i <= n;i++) cin >> q[i];int ju = ok();if (ju==-1){cout <<"Case "<<++kase<<": Not possible"<<endl;}else{cout <<"Case "<<++kase<<": Possible from station "<<ju<<endl;}}return 0;
}