题目分析
两个值:W、S
让我们想一想 最大的W S这头牛 在上边好还是在下面好
W表示自身重量 我们都有这个常识 体重大的在下面好一些 这样对底下的牛的压迫小
S代表能扛多沉 那越能抗的越在下面比较好 因为他能抗更多头牛在上面啊
所以综上,我们把每头牛的W、S相加 从小到大排序作为牛牛们从高到低的排列顺序即为最合理的
代码
#include<iostream>
using namespace std;
#include<algorithm>
typedef struct Node{
int w;
int s;
int sum;
bool operator <(struct Node cow) const{
return sum<cow.sum;
}
bool operator >(struct Node cow) const{
return sum>cow.sum;
}
}Node;
int main(void){
int n,w,s,sum;
cin>>n;
int weights[n+1];
weights[0]=0;
Node cows[n+1];
cows[0].sum=-0x3f3f3f3f;
for(int i=1;i<=n;i++){
cin>>w>>s;
sum=w+s;
cows[i].w=w,cows[i].s=s,cows[i].sum=sum;
}
sort(cows+1,cows+n+1);
int risk=0x3f3f3f3f,margin=0;
for(int i=1;i<=n;i++){
weights[i]=weights[i-1];
weights[i]+=cows[i].w;
margin=cows[i].s-weights[i-1];
risk=min(margin,risk);
}
risk=-risk;
cout<<risk;
}