Description
世界杯結束了,意大利人連本帶利的收回了法國人6年前欠他們的債,捧起了大力神杯,成就了4星意大利.Input
每組輸入數據分兩行,第一行是一個正整數n(1<=n<=100000),表示有n座城市.接下來的一行按照給定的路線順序的輸出這n個城市的生活費和花費,w1,l1,w2,l2,……,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 思路:先做相減的處理,然後就是有點像求序列最長的正整數和#include#include #include #include 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; }