HDU - 1422 重温世界杯

 3
2 
思路：先做相减的处理，然后就是有点像求序列最长的正整数和
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100005;

int arr[MAXN*3];
int n,dp[MAXN*3];
int sum[MAXN];

int main(){
	while (scanf("%d",&n) != EOF){
		for (int i = 1; i <= n; i++){
			int x,y;
			scanf("%d%d",&x,&y);
			arr[i] = x-y;
		}
	
		for (int i = 1; i <= n; i++)
			arr[i+n] = arr[i];
		memset(dp,0,sizeof(dp));
		int ans = 0;
		sum[0] = 0;
		arr[0] = 0;
		for (int i = 1; i <= n*2; i++){
			if (arr[i]+sum[i-1] >= 0){
				dp[i] = dp[i-1] + 1;
				sum[i] = arr[i] + sum[i-1];
				ans = max(ans,dp[i]);
				if (ans == n)
					break;
			}
			else if (arr[i] >= 0 && sum[i-1] < 0){
				dp[i] = 1;
				sum[i] = 0;
			}
			else {
				dp[i] = 0;
				sum[i] = 0;
			}
		}
		cout << ans << endl;
	}
	return 0;
}