USACO2005 Cow Acrobats前缀和 oj23402

题目大意：

N (1 ≤ N ≤ 50,000)头牛叠罗汉 找到最优排序使所有牛的风险值总和最小

每头牛重量 (1 ≤ W_i ≤ 10,000) 力量 (1 ≤ S_i ≤ 1,000,000,000)

自上往下编号1~n，第i头牛的风险值 = i~n的体重总和 - i的力量.

Input

* Line 1: A single line with the integer N.

* Lines 2..N+1: Line i+1 describes cow i with two space-separated integers, W_i and S_i.

Output

* Line 1: A single integer, giving the largest risk of all the cows in any optimal ordering that minimizes the risk.

Sample Input

310 32 53 3

Sample Output

2

Hint

OUTPUT DETAILS:

Put the cow with weight 10 on the bottom. She will carry the other two cows, so the risk of her collapsing is 2+3-3=2. The other cows have lower risk of collapsing.

 

观察规律：

假设一开始为最优排序

W = W(1) + W(2) + ... + W(i-1) 则

牛（i）风险 = W - S（i）

牛（i+1）风险 = W + W（i）- S（i+1）

若交换位置

牛（i+1）风险 = W - S（i+1）

牛（i）风险 = W + W（i+1）- S（i）

因为一开始为最优排序

所以 W + W（i）- S（i+1）< W + W（i+1）- S（i） 

则存在 W（i）+  S（i）< S（i+1）+ W（i+1）

#include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; int n,flag[50005]; long long m; struct dlh { long long w,s,sum; }d[50005]; bool cmp(struct dlh q,struct dlh p) { return q.sum>p.sum; } int main() { scanf("%d",&n); long long cnt=0,ans=-INF; for(int i=1;i<=n;i++) { scanf("%d%lld",&d[i].w,&d[i].s); cnt+=d[i].w; d[i].sum=d[i].w+d[i].s; } sort(d+1,d+1+n,cmp); for(int i=1;i<=n;i++) { cnt-=d[i].w; ans=max(ans,cnt-d[i].s); } printf("%d\n",ans); return 0; } View Code

 

转载于:https://www.cnblogs.com/zquzjx/p/8371755.html