六、贪心
没有思路的话，先排序。选择当前最好的情况来进行下去。
1.区间分组
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>//使每组内部区间不相交，按左端点从小到大排序
using namespace std;//从前往后处理每个区间，判断能否将其放到某个现有的组中。L[i]>Max_r。最大值
const int N = 100010;//如果不存在这样的组，则开新组，然后在将其放进去。
int n;//如果存在这样的组则将其放进去，并更新当前组
struct Range
{
int l,r;
bool operator< (const Range &W)const
{
return l<W.l;
}
}range[N];
int main()
{
scanf("%d", &n);
for(int i=0;i<n;i++)
{
int l,r;
scanf("%d%d",&l,&r);
range[i]={l,r};
}
sort(range,range+n);
priority_queue<int, vector<int>, greater<int>> heap;//优先队列,小根堆
for(int i=0;i<n;i++)
{
auto r= range[i];
if (heap.empty() || heap.top() >= r.l) heap.push(r.r);
else
{
heap.pop();
heap.push(r.r);
}
}
printf("%d\n",heap.size());
return 0;
}
2.huffman树，合并果子
最小的两个点深度一定最深，且可以互为兄弟
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;//开个优先队列，每次合并最小的两个点
int main()
{
int n;
cin>>n;
priority_queue<int, vector<int>, greater<int>> heap;//定义一个名为heap的小根堆
while (n -- )
{
int n;
cin>>n;
heap.push(n);//依序插入果子堆
}
int res=0;
while(heap.size()>1)//当还没有只剩一个堆时
{
int a=heap.top();heap.pop();//取第一个小值
int b=heap.top();heap.pop();//取第二小值
int c=b+a;//合并前两个小的
res=res+c;
heap.push(c);
}
cout<<res<<endl;
return 0;
}
3.排序不等式（排队打水）
从小到大排序
#include <iostream>
#include <cstring>//从小到大排序，总时间最小，最小的权值最大，则排在最低处
#include <algorithm>
using namespace std;
const int N = 100010;
typedef long long LL;
int main()
{
LL res=0;
int n;
int a[N];
cin>>n;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
sort(a,a+n);
for(int i=0;i<n;i++) res+=a[i]*(n-i-1);
printf("%lld\n",res);
return 0;
}
4.绝对值不等式，货仓选址
#include <iostream>//放中间最好，中位数
#include <cstring>
#include <algorithm>
const int N = 100010;
using namespace std;
int main()
{
int n;
cin>>n;
int a[N];
for(int i=0;i<n;i++) scanf("%d",&a[i]);
sort(a,a+n);
int res=0;
for(int i=0;i<n;i++) res+=abs(a[i]-a[n/2]);//每一个减去中位数取绝对值找距离
cout<<res<<endl;
return 0;
}
5.推公式，耍杂技的牛
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;//按照wi+si从小到大的顺序排，最大的危险系数一定是最小的
typedef long long ll;
typedef pair<int, int> PII;
const int N = 5e4 + 5;
PII a[N];
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++ )
{
int x, y;
scanf("%d %d", &x, &y);
a[i].first = x + y;
a[i].second = y;
}
sort(a, a + n);
ll res = -1e18, sum = 0;
for(int i = 0; i < n; i ++ )
{
sum -= a[i].second;
res = max(res, sum);
sum += a[i].first;
}
cout << res << endl;
return 0;
}