紫书 例题8-13 UVa 11093 （反证法）
这道题发现一个性质就解决了
如果以i为起点， 然后一直加油耗油， 到p这个地方要去p+1的时候没油了， 那么i， i+1， ……一直到p， 如果以这些点
为起点， 肯定也走不完。
为什么呢？
用反证法， 假设以q（i < q <= p）这个点为起点可以走完的话， 那么i这个点也一定可以走完
首先， i是可以达到q的， 因为i可以达到p， 而q是在p前面的， 而且从i开始走到q这个点剩下的油量肯定大于等于0，
而如果单纯从q开始走的话， 油量会等于0， 也就是说从i过来所有的油量反而会更多， 更容易走完
所以完全可以从i走到q， 再从q走完。
所以如果从i不能走完的话， 那么它经过的点就肯定不能走完了。
#include
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112345;
int a[MAXN], n;bool judge(int& pos)
{int num = 0, sum = 0;while(num < n && (sum += a[pos]) >= 0) num++, pos = (pos + 1) % n;return num == n;
}int main()
{int T, kase = 0, x;scanf("%d", &T);while(T--){scanf("%d", &n);REP(i, 0, n) scanf("%d", &a[i]);REP(i, 0, n) scanf("%d", &x), a[i] -= x;int start = 0, pos = 0, ok = true;while(!judge(pos)) {pos = (pos + 1) % n; //注意这里要+1， 能走到的最远的点一样要舍掉。 if(pos <= start) { ok = false; break;}start = pos;}if(ok) printf("Case %d: Possible from station %d\n", ++kase, start + 1);else printf("Case %d: Not possible\n", ++kase);}return 0;
} 转载于:https://www.cnblogs.com/sugewud/p/9819588.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！