贪心

【贪心】LuoguP1209 修理牛棚

【题目大意】参数\(M,S,C\)表示使用不超过\(M\)个区间覆盖\(C\)个点，其中\(c_i\)表示第\(i\)个点的位置编号，\(1\le c_i\le S\)，当\(L\le c_i\le R时，称[L,R]区间覆盖了第i个点\),求这些区间长度和的最小值，区间长度记为\(R-L+1\).

\(M\)越大，答案越小。升序排序\(c_i\)，当\(M=1\)时，\(ans=c_C-c_1+1\).考虑各点之间的空隙，理应有\((M-1)\)个空隙，贪心取最大空隙即可。

注意：\(L_{blank}=\max(0,c_{i+1}-c_i-1)\)

【贪心】LuoguP4053 建筑抢修

对于\(N\)个建筑，从时间0开始修理，给出每个建筑修理所需时间\(w_i\)与报废时刻\(t_i\)，同一时刻只能修理一个建筑，修理建筑的中途不能切换修理对象，求修理建筑数的最大值。

由于建筑修理成功的权值相同，可以考虑贪心。将建筑按\(t_i\)递增排序，记当前时间为\(Time\).

若\(Time+w_i\le t_i\)则将其加入以\(w_i\)为基准的大根堆中，

若\(Time+w_i> t_i\)判断\(w_i\)与\(q_{top}\)的大小关系，若小于，则抢修此建筑一定优于抢修堆顶的建筑，将其替换，\(Time=Time-q_{top}+w_i\)，否则放弃修理此建筑。

结果为\(q_{size}\)，算法时间复杂度为\(O(n\log n)\)

LuoguP4053 建筑抢修参考实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
long long Time;
int n;
struct node{int w,t;}a[N];
bool cmp(node x,node y){return x.t<y.t;}
std::priority_queue<int> q;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].w,&a[i].t);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(Time+a[i].w<=a[i].t) 
            q.push(a[i].w),Time+=a[i].w;
        else
        {
            if(a[i].w<q.top())
            {
                Time+=a[i].w-q.top();
                q.pop(),q.push(a[i].w);
            }
        }
    }
    cout<<q.size();
    return 0;
}