從第一個加油站開始遍歷，如果到第k個加油站沒有油了，那第1,2,3,4····k加油站肯定也不行 復雜度O（n）

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; const int maxn = 200000+100; int p[maxn], q[maxn]; int T, n;int main() {int Case = 0;scanf("%d", &T);while(T--) {scanf("%d", &n);int res1 = 0, res2 = 0;memset(p, 0, sizeof(p));memset(q, 0, sizeof(q));for(int i = 0; i < n; ++i) {scanf("%d", &p[i]);res1 += p[i];}for(int i = 0; i < n; ++i) {scanf("%d", &q[i]);res2 += q[i];}printf("Case %d: ", ++Case);if(res1 < res2) { printf("Not possible\n"); continue; }int sum = 0, id = 1, is = 0;for(int i = 0; i < n; ++i) {sum += p[i];sum -= q[i];if(sum < 0) {sum = 0;id = i+2;}}printf("Possible from station %d\n", id);}return 0; }

總結

以上是生活随笔為你收集整理的uva 11093的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。