第六章贪心（二）（排序不等式、绝对值不等式、推公式）

本文主要是介绍第六章贪心（二）（排序不等式、绝对值不等式、推公式），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

（一）排序不等式

913 排队打水，每个人都有自己杯子的容量

从小到大排序，总时间最小；

#include<bits/stdc++.h>
using namespace std;
//148 合并果子
const int N=1e5+10;int main()
{priority_queue< int,vector<int>,greater<int> >heap;long long int n;cin>>n;for(int i=0;i<n;i++){int num;cin>>num;heap.push(num);}long long int sum=0,cnt=0;while(heap.size()>1){cnt+=heap.top();heap.pop();sum+=cnt;}cout<<sum<<endl;}

y做法：当排好队后，每个人的等待时间长短已经确定

#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 100010;int n;
int t[N];int main()
{scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d", &t[i]);sort(t, t + n);reverse(t, t + n);LL res = 0;for (int i = 0; i < n; i ++ ) res += t[i] * i;printf("%lld\n", res);return 0;
}作者：yxc
链接：https://www.acwing.com/activity/content/code/content/79272/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二、绝对值不等式

104 货仓的选择

给定多个固定的商店，然后确定一个仓库的位置，要求仓库到所有商店的距离总和最小

最后选择所有点的中位数。作为仓库

语法：实现降序排序的方法

 sort(a, a + n, greater<int>());

#include<bits/stdc++.h>
using namespace std;
//104 货仓选址
const int N=1e5+10;
int a[N];
int main()
{int n;cin>>n;for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);int ans=0;for(int i=0;i<n;i++){ans+=abs(a[i]-a[n/2]);}cout<<ans<<endl;return 0;
}

三、推公式

（一）125 耍杂技的牛

把相同的去掉：

加上si +si+1

交换后的最大值一定小于交换之前。依次为a,b,c,d;

其中a一定大于c，a也一定大于d，所以 c和d的最大值一定是小于b的。所以在排序后，从上到下。从大到小叠牛，改变任意两个牛的序列一定是让最大值的最小值变小的。贪心得到的结果不会让最后的结果变大。

#include<bits/stdc++.h>
using namespace std;
//125 耍杂技的牛
const int N=5e4+10;
typedef pair<int,int> PII;
int n;
PII cow[N];
int main()
{cin>>n;for(int i=0;i<n;i++){int w,s;cin>>w>>s;cow[i]={w+s,s};}sort(cow,cow+n);int res=-2e9;int sum=0;for(int i=0;i<n;i++){res=max(res,sum-cow[i].second);sum+=cow[i].first-cow[i].second;}cout<<res<<endl;}