【題目描述】：John 打算駕駛一輛汽車周游一個環(huán)形公路。公路上總共有n個車站，每個站都有若干升汽油（有的站可能油量為零），每升油可以讓汽車行駛一千米。John 必須從某個車站出發(fā)，一直按順時針（或逆時針）方向走遍所有的車站，并回到起點(diǎn)。在一開始的時候，汽車內(nèi)油量為零，John 每到一個車站就把該站所有的油都帶上（起點(diǎn)站亦是如此），行駛過程中不能出現(xiàn)沒有油的情況。任務(wù)：判斷以每個車站為起點(diǎn)能否按條件成功周游一周。 【輸入描述】：第一行是一個整數(shù)n，表示環(huán)形公路上的車站數(shù)；接下來n行，每行兩個整數(shù)pi,di分別表示表示第i號車站的存油量和第i號車站到下一站的距離。 【輸出描述】：輸出共n行，如果從第i號車站出發(fā)，一直按順時針（或逆時針）方向行駛，能夠成功周游一圈，則在第i行輸出 TAK，否則輸出 NIE。 【樣例輸入】：5 3 1 1 2 5 2 0 1 5 4【樣例輸出】：TAK NIE TAK NIE TAK【時間限制、數(shù)據(jù)范圍及描述】：時間：2s 空間：512M30%的數(shù)據(jù)：3<=n<=10^4；70%的數(shù)據(jù)：3<=n<=10^5；100%的數(shù)據(jù)：3<=n<=10^6；0<=pi<=2×10^9；0<di<=2×10^9；本題的暴力做法是將數(shù)組拓寬2倍,對其做一遍前綴和,每次對長度為n的序列進(jìn)行區(qū)間減法,減去前一位數(shù),即得到此長度為n的序列的前綴和, 然后看其中最小的是否>=0,一共做n次,然后統(tǒng)計(jì)答案即可.(這里的區(qū)間減法可以直接簡化成求區(qū)間最小,然后判斷其是否>=前一位數(shù)) 正解做法即用單調(diào)隊(duì)列維護(hù)區(qū)間最小的數(shù)即可. 注意:每個站到下一個站的距離是順時針給出的.Code: #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<ctime> using namespace std; const int N=2000005; long long sum[N]; int n,p[N],d[N],ok[N],Q[N]; void DP1(){int head=1,tail=0;for(int i=1;i<=n;i++){while(head<=tail&&sum[Q[tail]]>=sum[i]){--tail;}Q[++tail]=i;}for(int i=n+1;i<=2*n;i++){while(head<=tail&&sum[Q[tail]]>=sum[i]){--tail;}Q[++tail]=i;while(head<=tail&&Q[head]<=i-n-1){++head;}if(sum[Q[head]]>=sum[i-n-1]){ok[i-n]=1;}} } void DP2(){int head=1,tail=0;for(int i=n*2;i>=n+1;i--){while(head<=tail&&sum[Q[tail]]>=sum[i]){--tail;}Q[++tail]=i;}for(int i=n;i>=1;i--){while(head<=tail&&sum[Q[tail]]>=sum[i]){--tail;}Q[++tail]=i;while(head<=tail&&Q[head]>=i+n){++head;}if(sum[Q[head]]>=sum[i+n]){ok[i]=1;}} } int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&p[i],&d[i]);p[i+n]=p[i];d[i+n]=d[i];sum[i]=sum[i-1]+p[i]-d[i];}for(int i=n+1;i<=n*2;i++){sum[i]=sum[i-1]+p[i]-d[i];}DP1();for(int i=n*2;i>=1;i--){sum[i]=sum[i+1]+p[i+1]-d[i];}DP2();for(int i=1;i<=n;i++){if(ok[i]){printf("TAK\n");}else{printf("NIE\n");}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/ukcxrtjr/p/11531260.html

總結(jié)

以上是生活随笔為你收集整理的UOJ #586. 旅行问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。