ワールドカップ(最長連続と非負のサブシーケンス)を再温める

W杯を温める
dianwo 
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5305    Accepted Submission(s): 1817
Problem Description
ワールドカップが終わって、イタリア人は元利を持ってフランス人が6年前に借りた借金を回収して、力の神杯を持って、4つ星のイタリアを成し遂げました.
ワールドカップは終わったが、このワールドカップは私たちに多くの思い出を残した.例えば、私たちは黄名口の3分間の情熱的な解説を聞いて、私たちは同じ人に3枚のイエローカードを提示することができることを知っていた.私たちはジダンの頭がボールを上げるだけでなく、人を支えることもできることを見た.
こんなにたくさんのすばらしさがあって、xhdはドイツのワールドカップを温めることを决めて、もちろんそれぞれのワールドカップの试合を引き受ける都市に行ってみるだけです.しかし、これはお金より大きい必要があります.幸いなことに、xhdのワールドカップに対する爱の情はドイツのワールドカップの组织委员会を感动させて、彼らはxhdが中国杭州とドイツの任意のワールドカップの都市の往复の航空券を提供します.これらの都市を説得してxhdがこの都市に着いた時に彼に生活費を提供して彼がそこで見学する時に使うようにして、見学が終わった時に残りのお金もxhdに残しますが、生活費が足りない時彼らはxhdの今回のドイツの旅を強制的に終わらせます.それ以外に、彼らはもう一つの条件があります.xhdは彼らが与えたルートによって見学するしかありません.例えば3つの都市a,b,cがあります.彼らはa-b-c-aのルートを与えて、それではxhdは3種類の見学の順序abc、bca、cabだけあって、各都市が提供する生活費とそこでの費用がすべて異なっているため、xhdはとても頭が痛くて、幸いにも私达は事前にこの生活費と費用を知っていました.
 
 
Input
各入力データは2行に分けられ、1行目はn(1<=n<=10000000)の正の整数n(1<=n<=10000000)であり、n個の都市があることを示す.次の行は、n個の都市の生活費と費用を所定のルート順に出力し、w 1,l 1,w 2,l 2,…,wn,ln,wi,liはそれぞれi個目の都市の生活費と費用を表し、それらはいずれも正の整数である.
 
 
Output
各グループのデータに対応して最も見学可能な都市数を出力する.
 
 
Sample Input
3
3 2 3 4 2 2
3
3 2 3 4 2 3
 
 
Sample Output
3
2
サイクルの両側、ちょうどトップサイクル===============================T T_T T_T

 1 #include <cstdlib>
 2 #include <cstdio>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 int main(int argc, char *argv[])
 8 {
 9     int n, a, b;
10     while (scanf("%d", &n)!=EOF)
11     {
12         int i, j, res[100000], max=0, count=0,flag=0, temp=0;
13         for (i=0; i<n; i++)
14         {
15             scanf("%d%d", &a, &b);
16             res[i] = a - b;
17             temp += res[i];
18             if (temp >= 0)
19                 count++;
20             else
21             {
22                 count = 0;
23                 temp = 0;
24             }     
25             if (count > max)
26                 max = count;
27         }
28         for(i=0;i<n;i++)
29         {
30             temp += res[i];
31             if (temp >= 0)
32                 count++;
33             else
34             {
35                 count = 0;
36                 temp = 0;
37             }     
38             if (count > max)
39                 max = count;
40         }
41         printf("%d
", max>n?n:max);  
42     }
43     //  system("PAUSE");
44     return 0;
45 }