网络优化

贪心还是得保证正确再写,不难就挺难受的,这个题的贪心解法讲出来挺容易的,就是按r排序从小到大排,然后分配区间[L,R].这里也从小到大分配,能分配就分配,这样就必定是最优解了.因为我从小到大分配的R,这样的R去分配L,是不影响后面的.但是这样做的复杂度是O(N^2)的.显然太高了.我们不妨用优先队列来优化,优先队列开两维,一维是区间r,二维是权值val.我们从小到大扫描每个位子,看它是不是可以被我优先队列的元素覆盖,当然假如可以被覆盖那我就先用R区间较小的就好了.
ac代码如下:

//不要乱贪心...
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
struct vv{
    int l,r,v;
}a[N];
bool cmp(vv x,vv y)
{
    if(x.l==y.l&&x.r==y.r)    return x.v<y.v;
    else if(x.l==y.l)         return x.r<y.r;
    else                      return x.l<y.l;
}
int n,m;
struct av{
    int R,V;
    friend bool operator<(struct av x,struct av y)
    {
        if(x.R==y.R)    return x.V>y.V;
        else            return x.R>y.R;
    }
};

int main()
{
    while(cin>>n>>m)
    {
        priority_queue<av>q;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].v);
        }sort(a+1,a+1+m,cmp);
        int id=1,ans=0;
        for(int i=1;i<=n;i++)
        {
            while(a[id].l==i)    {  q.push({a[id].r,a[id].v}),id++;  }
            while(q.size()&&(q.top().R<i||q.top().V==0))   {  q.pop(); }
            if(!q.size())    continue;
            auto t=q.top();
            q.pop();t.V--;
            q.push(t);
            ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}