EOJ3263:丽娃河的狼人传说（贪心）

传送门

题意

分析

考虑将区间按右端点排序，再遍历区间，操作即可

建议以加方式写

trick

1.不需要判区间重合

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int t;

int n,m,k;

int a[1010];

struct node

{

    int l,r,num;

    bool operator<(const node &p)const

    {

        return r==p.r?l>p.l:r<p.r;

    }

}c[1010];

int main()

{

    scanf("%d",&t);

    for(int q=1;q<=t;++q)

    {

        scanf("%d %d %d",&n,&m,&k);

        memset(a,0,sizeof(a));

        int x;

        for(int i=1;i<=k;++i)

        {

            scanf("%d",&x);a[x]=1;

        }

        for(int i=1;i<=m;++i)

        {

            scanf("%d %d %d",&c[i].l,&c[i].r,&c[i].num);

        }

        sort(c+1,c+1+m);

        int ans=0,flag=0;

        for(int i=1;i<=m;++i)

        {

            if(c[i].r-c[i].l+1<c[i].num) { flag=1;break; }

            int ret=0;

            for(int j=c[i].l;j<=c[i].r;++j) ret+=a[j];

            if(ret>=c[i].num) continue;

            ans+=c[i].num-ret;

            int cnt=0;

            for(int j=c[i].r;j>=c[i].l;--j)

            {

                if(a[j]==0)

                {

                     a[j]=1;cnt++;

                     if(cnt==c[i].num-ret) break;

                }

            }

        }

        printf("Case %d: %d\n",q,flag?-1:ans);

    }

    return 0;

}