EOJ------丽娃河的狼人传说

柔情只为你懂 2022-06-15 03:22 189阅读 0赞

## 丽娃河的狼人传说 ##

**Time limit per test:** 1.0 seconds

**Time limit all tests:** 1.0 seconds

**Memory limit:** 256 megabytes

丽娃河是华师大著名的风景线。但由于学校财政紧缺，丽娃河边的路灯年久失修，一到晚上就会出现走在河边要打着手电的情况，不仅非常不方便，而且影响安全：已经发生了大大小小的事故多起。

![river.a17eb81b44921b37a3a2d31c17a20315.jpg][]

方便起见，丽娃河可以看成是从 1![Image 1][] 到 *n*![Image 1][] 的一条数轴。为了美观，路灯只能安装在整数点上，每个整数点只能安装一盏路灯。经专业勘测，有 *m*![Image 1][] 个区间特别容易发生事故，所以至少要安装一定数量的路灯，

请问至少还要安装多少路灯。

### Input ###

第一行一个整数 *T*![Image 1][] (1≤*T*≤300)![Image 1][]，表示测试数据组数。

对于每组数据：

*  第一行三个整数 *n*,*m*,*k*![Image 1][] (1≤*n*≤10![Image 1][]3![Image 1][],1≤*m*≤10![Image 1][]3![Image 1][],1≤*k*≤*n*)![Image 1][]。
 *  第二行 *k*![Image 1][] 个不同的整数用空格隔开，表示这些位置一开始就有路灯。
 *  接下来 *m*![Image 1][] 行表示约束条件。第 *i*![Image 1][] 行三个整数 *l*![Image 1][]*i*![Image 1][],*r*![Image 1][]*i*![Image 1][],*t*![Image 1][]*i*![Image 1][]![Image 1][] 表示：第 *i*![Image 1][] 个区间 \[*l*![Image 1][]*i*![Image 1][],*r*![Image 1][]*i*![Image 1][]\]![Image 1][] 至少要安装 *t*![Image 1][]*i*![Image 1][]![Image 1][] 盏路灯 (1≤*l*![Image 1][]*i*![Image 1][]≤*r*![Image 1][]*i*![Image 1][]≤*n*,1≤*t*![Image 1][]*i*![Image 1][]≤*n*)![Image 1][]。

### Output ###

对于每组数据，输出 `Case x: y`。其中 x 表示测试数据编号（从 1 开始），y 表示至少要安装的路灯数目。如果无解，y 为 −1![Image 1][]。

### Examples ###

Input

3
    5 1 3
    1 3 5
    2 3 2
    5 2 3
    1 3 5
    2 3 2
    3 5 3
    5 2 3
    1 3 5
    2 3 2
    4 5 1

Output

Case 1: 1
    Case 2: 2
    Case 3: 1

错误的：

//#include <iostream>
    //#include <cstdio>
    //#include <cstring>
    //#include <string>
    //#include <algorithm>
    //using namespace std;
    //int main()
    //{
    //    int t,n,m,k,a[1005],b,x,y,d;
    //    int cas=1;
    //    scanf("%d",&t);
    //    while(t--)
    //    {
    //        int ok=0;
    //        memset(a,0,sizeof(a));
    //        scanf("%d %d %d",&n,&m,&k);
    //        for(int i=0;i<k;i++)
    //        {
    //            scanf("%d",&b);
    //            a[b]=1;
    //        }
    //        int sum=0;
    //        for(int i=0;i<m;i++)
    //        {
    //            int ans=0;
    //            scanf("%d %d %d",&x,&y,&d);
    //            for(int j=x;j<=y;j++)
    //            {
    //                if(a[j])
    //                    ans++;
    //            }
    //            if(d-ans>y-x+1)
    //                ok=1;
    //            if(ans<d)
    //            sum+=d-ans;
    //            int s=1;
    //            for(int j=x;j<=y&&s<=d-ans;j++)
    //            {
    //                if(a[j]==0)
    //                {
    //                    a[j]=1;
    //                }
    //            }
    //        }
    //        printf("Case %d: %d\n",cas++,ok==1?-1:sum);
    //    }
    //    return 0;
    //}

AC的了

#include <bits/stdc++.h>
    using namespace std;
    bool vis[1005];
    struct ode
    {
        int left,right,need;
    }node[10005];
    
    bool cmp(ode a,ode b)
    {
        if(a.right==b.right)
            return a.left<b.left;
        else
            return a.right<b.right;
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        int Case=0;
        while(t--)
        {
            memset(vis,0,sizeof(vis));
            int n,m,k,x;
            scanf("%d%d%d",&n,&m,&k);
            for(int i=0;i<k;i++)
            {
                scanf("%d",&x);
                vis[x]=1;//有路灯就标记为1
            }
            int ans=0;
            for(int i=0;i<m;i++)
                scanf("%d%d%d",&node[i].left,&node[i].right,&node[i].need);
            sort(node,node+m,cmp);
            for(int i=0;i<m;i++)
            {
                if(node[i].right-node[i].left+1<node[i].need)//如果需要安装的路灯个数大于区间了，当然就是不可能了，输出-1；
                {
                    ans=-1;
                    break;
                }
                int tmp=0;
                for(int k=node[i].left;k<=node[i].right;k++)
                {
                    if(vis[k])//计算node[i].left和node[i].right这个区间路灯的个数
                        tmp++;
                }
                if(tmp<node[i].need)//只有当这个区间的路灯个数小于需要安装的个数时才安装
                    ans=ans+node[i].need-tmp;//ans就是这些区间需要安装的个数的累加，
                tmp = node[i].need-tmp;//tmp就是需要某一个区间需要安装的个数
                for(int h=node[i].right;h>=node[i].left && tmp>0;h--)//安装了tmp个路灯，那就要标记tmp个点，
                //而且是要在靠近右边安装，因为靠右，就是靠近下一个区间，靠近下一个区间，那下一个区间就会包含更多路灯，从而就只需安装更少的路灯了
                {
                    if(vis[h]==0)//没有路灯，就安装一个
                    {
                        tmp--;
                        vis[h]=1;
                    }
                }
            }
            printf("Case %d: %d\n", ++Case, ans);
        }
        return 0;
    }

[river.a17eb81b44921b37a3a2d31c17a20315.jpg]: /images/20220615/ba85ebbca3e94573ae91086b7516debc.png
[Image 1]: