算法·贪心

区间

区间选点

• 将每个区间按照右端点从小到大排序

• 从前往后依次枚举每个区间

  • 如果当前区间中已经包含点，则直接pass
  • 否则选择当前区间的右端点

#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
int n;
struct Range{
    int l,r;
    bool operator< (const Range &w)const 
    {
        return r<w.r;
    }
}range[N];
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int l,r;
        cin >> l>>r;
        range[i]={l,r};
    }
    sort(range,range+n);
    int res=0,ed = -2e9;
    for(int i=0;i<n;i++)
        if(range[i].l>ed){
            res++;
            ed=range[i].r;
        }
    cout<<res;
    return 0;
}

区间分组

#include <iostream>
#include <algorithm>
using namespace std;
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(){
    cin>>n;
    for(int i=0;i<n;i++){
        int l,r;
        cin >> 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);//如果小根堆为空或者l找不到比他小的右端点（由于是小根堆，heap.top()是所有r里面最小的，说明l和堆里面存的任一已有区间存在交集，需要另开数组存入。
    else {//说明能够找到左端点大于的右端点，可以加入区间
        heap.pop();//删除堆顶元素,因为堆顶元素的区间加入了新的线段，右端点被更新了
        heap.push(r.r);
    }
        }
    cout<<heap.size();
    return 0;
}

区间覆盖

#include <iostream>
#include <algorithm>

using namespace std;

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()
{
    int st, ed;
    scanf("%d%d", &st, &ed);
    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);

    int res = 0;
    bool success = false;
    for (int i = 0; i < n; i ++ )
    {
        int j = i, r = -2e9;
        while (j < n && range[j].l <= st)//遍历所有区间，更新l小于线段左边，右边端点的最大值
        {
            r = max(r, range[j].r);
            j ++ ;
        }

        if (r < st)//如果最大值都在线段左边，说明没法覆盖
        {
            res = -1;
            break;
        }

        res ++ ;//找到一个新区间
        if (r >= ed)//此时在l<st的前提下，r>ed，说明已经完全覆盖
        {
            success = true;//已找到，退出
            break;
        }

        st = r;//找到一个区间，但未能覆盖末尾，寻求下一个区间，将起点更新为新找到的终点r，将已覆盖的线段切去。
        i = j - 1;//range已经按照左端点从小到大排，此时的j为左端点小于等于st的最大值，此区间包括之前的区间已经使用过，由于j++,此时的区间序号应该是j-1，即下一轮要从j-1,即不符合条件的第一个开始遍历
    }

    if (!success) res = -1;
    printf("%d\n", res);

    return 0;
}

Huffman树

• 一颗完全二叉树，每一个点都有左右孩子
• 所有的叶子节点就是要合并的点
• 所有的内部点都是由某些点合并过来的点

合并果子

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int main(){
int n;
cin>>n;
priority_queue<int,vector<int>,greater<int>>heap;
while(n--){
   int x;
   cin>>x;
   heap.push(x);
}
int res=0;
while(heap.size()>1){
int a=heap.top();heap.pop();
int b=heap.top();heap.pop();
res+=a+b;
heap.push(a+b);
}
	cout<<res;
	return 0;
}

排序不等式

//打水问题
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N-100010;
int n;
int t[N];
int main(){
    cin >>n;
    for(int i =0;i<n;i++)
        cin>>t[i];
    sort(t,t+n);
    LL res=0;
    for(int i = 0;i<n;i++)res+=t[i]*(n-i-1);
    cout<<res;
    return 0;
}

绝对值不等式

//仓库选址
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
int n;
int a[N];
int main(){
    cin>>n;
    for(int i= 0;i<n;i++) cin>>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;
    return 0;
}

推公式

#include <iostream>
#include <algorithm>
using namespace std;
const int N=50010;
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,w};
    }
    sort(cow,cow+n);
    int res=-2e9,sum=0;
    for(int i =0;i<n;i++){
        int w=cow[i].second,s=cow[i].first-w;
        res = max(res,sum-s);
        res+=w;
        
    }
    cout<<res;
    return 0;
}