Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5823 Accepted Submission(s): 2039
题解:
因为可以构成一个环,所以可以把前面的n-1复制到后面
s[n+1]=s[1];s[n+2]=s[2]......
之后就很简单了,在保证sum>=0的情况下求最多能访问多少个城市。
数组开小了显示竟然超时,让我很郁闷;
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> using namespace std; const int INF=0x3f3f3f3f; #define mem(x,y) memset(x,y,sizeof(x)) #define SI(x) scanf("%d",&x) #define PI(x) printf("%d",x) #define SD(x) scanf("%lf",&x) #define P_ printf(" ") typedef long long LL; const int MAXN=200010; int w[MAXN],l[MAXN]; int main(){ int N; while(~scanf("%d",&N)){ for(int i=1;i<=N;i++)SI(l[i]),SI(w[i]); for(int i=N+1,j=1;i<=2*N;i++,j++){ w[i]=w[j];l[i]=l[j]; } int money=0; int cur=0,ans=0; for(int i=1;i<=2*N-1;i++){ money+=l[i]; money-=w[i]; if(money<0){ ans=max(ans,cur); if(ans>=N)break; cur=0; money=0; } else cur++; } ans=max(ans,cur); if(ans>=N)ans=N; printf("%d\n",ans); } return 0; }
原文:http://www.cnblogs.com/handsomecui/p/5205067.html