BUPT2017 wintertraining(16) #4 B

POJ - 3045

题意

n(1 <= N <= 50,000) 个牛，重wi (1 <= W_i <= 10,000)，力气si (1 <= S_i <= 1,000,000,000)，堆成一个竖线，risk值为每只牛上面的w之和-它的si，使它的最大值最小，输出最小值。

题解

根据数据范围也可以知道要贪心。

wi和si之和小的放上面。不要漏掉最top的牛的risk值。

证明：设i,j是相邻的两只牛，tot为i、j上面的wi值之和，r_i为i的risk。

若i在j上面则

若j在i上面则

可以观察到(1)>(4),(3)>(2),要是(1)>(3)，也就是 j 在 i 上面更优，则有\(w_i+s_i>w_j+s_j\)。

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#define ll long long

using namespace std;

struct cow{

	ll w,s;

	bool operator < (const cow&b)const{

		return w+s<b.w+b.s;

	}

}a[50005];

int main() {

	int n;

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		scanf("%lld%lld",&a[i].w,&a[i].s);

	sort(a+1,1+a+n);

	ll ans=-a[1].s,tot=0;

	for(int i=2;i<=n;i++){

		tot+=a[i-1].w;

		ans=max(ans,tot-a[i].s);

	}

	printf("%lld",ans);

	return 0;

}