题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1422
主要是处理正子段长度有点麻烦
直接将在保存的数据后面再接上1…n的数据,这样扫描一遍的复杂度为n;再加一个优化, 当Dp[i]==n时,也就是能全部游完所有城市的时候,直接break;
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=100000+5;
int n[maxn],d[maxn];
int main(int argc, char const *argv[])
{int N,w,l;while(scanf("%d",&N)!=EOF){memset(n,0,sizeof(n));for (int i = 0; i < N; ++i){scanf("%d%d",&w,&l);n[i]=w-l;}int temp=0,ans=0;memset(d,0,sizeof(d));for (int i = 0; i < 2*N; ++i){if(temp>=0) temp+=n[i%N];else temp=n[i%N];if(temp>=0) d[i%N]=d[(i-1)%N]+1;else d[i%N]=0;ans=max(ans,d[i%N]);if(ans==N) break;}cout<<ans<<endl;}return 0;
}