题目描述
这道题与耍杂技的牛
是一个问题
思想
题目已经说明只要排列成一列那么就会获得最小的风险值,但是完全没有思路
1. 题目提示了要进行排序,要么升序,要么降序,当然是可以进行下去的,只不过在分析时只看到了要对质量进行升序,那样可以保证-力量之后尽可能的小。
这样去想的话,那么力量也最好是升序排列。
2. 根据做题经验的累积,这种情况下,要么+ -,不会出现乘除,所以就是在w+s升序的排列下会得到一个最小的最大风险值。
那么如果想要严谨一些的话,应该去证明这个结论是否满足我们的猜想,这个证明过程已经证明过,就像视频中那么证明即可
3. 最重要的是,举出较少的例子去进行佐证证明是很容易的
4. 这个题目要学习的除了思想,还有就是排序的自定义排序函数的学习,以及对于结构体的应用。
样例
3
10 3
2 5
3 3
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+ 10;
struct node{
int w,s,sum;
}Node[N];
int ans = -0x3f3f3f3f, presum;
bool cmp(node a,node b)
{
return a.sum < b.sum;
}
int main(){
int n;
cin>>n;
for(int i = 1;i <= n;i++)
{
cin>>Node[i].w >> Node[i].s;
Node[i].sum = Node[i].w + Node[i].s;
}
sort(Node + 1, Node + n + 1, cmp);
for(int i = 1;i <= n;i++)
{
presum += Node[i - 1].w; // 考虑当前盾卫为i,前i - 1个的质量和-s就是风险值
ans = max(ans, presum - Node[i].s);
}
cout << ans <<endl;
return 0;
}