首页 > 代码库 > UVa11093 Just Finish it up (模拟)
UVa11093 Just Finish it up (模拟)
链接：http://vjudge.net/problem/UVA-11093
分析：模拟，枚举起点（0~n-1），假定从某一起点s出发，途中遇到了某个加油站p，在从它开到加油站p+1时油没了，这样以s+1,s+2,...,p为起点的一定不是解，直接将起点跳到p+1开始枚举，时间复杂度为O（n）。
1 #include <cstdio> 2 3 const int maxn = 100005; 4 5 int n, p[maxn], q[maxn]; 6 7 int go(int n) { 8 for (int st = 0; st < n; st++) { 9 int fuel = 0, i;10 for (i = 0; i < n; i++) {11 fuel += p[(st+i)%n] - q[(st+i)%n];12 if (fuel < 0) { st += i; break; }13 }14 if (i == n) return st;15 }16 return -1;17 }18 19 int main() {20 int T;21 scanf("%d", &T);22 for (int kase = 1; kase <= T; kase++) {23 scanf("%d", &n);24 for (int i = 0; i < n; i++) scanf("%d", &p[i]);25 for (int i = 0; i < n; i++) scanf("%d", &q[i]);26 int ans = go(n);27 printf("Case %d: ", kase);28 if (ans < 0) printf("Not possible\n");29 else printf("Possible from station %d\n", ans + 1);30 }31 return 0;32 }
UVa11093 Just Finish it up (模拟)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。