丽娃河的狼人传说 Time limit per test: 1.0 seconds Time limit all tests: 1.0 seconds Memory limit: 256 megabytes 丽娃河是华师大著名的风景线。但由于学校财政紧缺，丽娃河边的路灯年久失修，一到晚上就会出现走在河边要打着手电的情况，不仅非常不方便，而且影响安全：已经发生了大大小小的事故多起。 方便起见，丽娃河可以看成是从 1 到 n 的一条数轴。为了美观，路灯只能安装在整数点上，每个整数点只能安装一盏路灯。经专业勘测，有 m 个区间特别容易发生事故，所以至少要安装一定数量的路灯， 请问至少还要安装多少路灯。 Input 第一行一个整数 T (1≤T≤300)，表示测试数据组数。 对于每组数据： 第一行三个整数 n,m,k (1≤n≤103,1≤m≤103,1≤k≤n)。 第二行 k 个不同的整数用空格隔开，表示这些位置一开始就有路灯。 接下来 m 行表示约束条件。第 i 行三个整数 li,ri,ti 表示：第 i 个区间 [li,ri] 至少要安装 ti 盏路灯 (1≤li≤ri≤n,1≤ti≤n)。 Output 对于每组数据，输出 Case x: y。其中 x 表示测试数据编号（从 1 开始），y 表示至少要安装的路灯数目。如果无解，y 为 −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 Note 因为今天不是满月，所以狼人没有出现。 Source 2017 华东师范大学网赛 /** 题目：Problem #3263 丽娃河的狼人传说 链接：http://acm.ecnu.edu.cn/problem/3263/ 题意：给定一个数n，表示一个1-n的数轴，给定一个k，表示数轴上k个位置已经安装了灯。给定一个m，表示有m个区间[l,r]， 每个区间后面有个整数值表示在这个区间至少要有多少盏灯。l,r都是整数。灯只可以安装在数轴的整数点上。 问至少要安装多少盏灯，才能使所有区间都满足自己要求的条件。如果无解，输出-1. 思路：贪心，对r进行排序即可。 */ #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> P; const int maxn = 1e5+100; int T, n, m, k; int lgt[1005]; struct node { int l, r, t; bool operator < (const node&k)const { return r<k.r; } }a[1005]; int main() { cin>>T; int cas = 1; while(T--) { scanf("%d%d%d",&n,&m,&k); memset(lgt, 0, sizeof lgt); for(int i = 1; i <= k; i++){ int x; scanf("%d",&x); lgt[x] = 1; } int flag = 0; for(int i = 0; i < m; i++){ scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].t); if(a[i].r-a[i].l+1<a[i].t){flag = 1;} } if(flag){ printf("Case %d: -1 ",cas++) ; continue; } sort(a,a+m); int ans = 0; for(int i = 0; i < m; i++){ int l = a[i].l, r = a[i].r; int cnt = 0; for(int j = l; j <= r; j++){ cnt += lgt[j]; } if(cnt>=a[i].t) continue; cnt = a[i].t-cnt; for(int j = r; j >= l&&cnt; j--){ if(lgt[j]==0){ lgt[j] = 1; cnt--; ans ++; } } } printf("Case %d: %d ",cas++,ans); } return 0; }