• 周一. 8月 15th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

洛谷 P1842 [USACO05NOV]奶牛玩杂技(贪心)

admin

11月 28, 2021

传送门


解题思路

(i,j) 相邻,前面的重量和为 (x)
(i) 在上面更优,则

[max(x-s[i],x+w[i]-s[j])<max(x-s[j],x+w[j]-s[i])
]

(x-s[i]) 一定小于 (x+w[j]-s[i])
(x-s[j]) 一定小于 (x+w[i]-s[j])
所以上述式子可以化简为:

[x+w[i]-s[j]< x+w[j]-s[i]
]

[w[i]+s[i]<w[j]+s[j]
]

所以按照 (w+s) 升序排序即可。

AC代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<bitset>
#include<cstdio>
#include<ctime>
using namespace std;
const int maxn=5e4+5;
int n;
long long ans=-1e9,now;
struct node{
	int a,b;
}x[maxn];
bool cmp(node a ,node b){
	return a.a+a.b<b.a+b.b;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>x[i].a>>x[i].b;
	}
	sort(x+1,x+n+1,cmp); 
	for(int i=1;i<=n;i++){
		ans=max(ans,now-x[i].b);
		now+=x[i].a; 
	}
	cout<<ans;
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。