本文主要是介绍3263 丽娃河的狼人传说，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
丽娃河的狼人传说
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
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
Case 1: 1 Case 2: 2 Case 3: 1
Note
因为今天不是满月，所以狼人没有出现。
Source
2017 华东师范大学网赛#include<bits/stdc++.h>
#define LL long long
#define MEM(a, b) memset(a, b, sizeof(a))
using namespace std;
int vis[1005];
struct Node
{int li, ri, ti;
};
Node data[1005];
bool cmp(Node a, Node b)
{return a.ri < b.ri;
}
int main()
{int T, CAS = 0;scanf("%d", &T);while(T--){MEM(vis, 0);int n, m, k;scanf("%d %d %d", &n, &m, &k);int t;for(int i = 0 ; i < k ; i++){scanf("%d", &t);vis[t] = 1;}bool ok = true;for(int i = 0 ; i < m ; i++){scanf("%d %d %d", &data[i].li, &data[i].ri, &data[i].ti);if(data[i].ri - data[i].li + 1 < data[i].ti)ok = false;}if(!ok){printf("Case %d: -1\n", ++CAS);continue;}sort(data, data + m, cmp);int ans = 0;for(int i = 0 ; i < m ; i++){int cnt = 0;for(int a = data[i].li ; a <= data[i].ri ; a++)if(vis[a]) cnt++;if(cnt < data[i].ti){cnt = data[i].ti - cnt;ans += cnt;for(int a = data[i].ri ; a >= data[i].li ; a--){if(vis[a] == 0){vis[a] = 1;cnt--;}if(cnt <= 0) break;}}}printf("Case %d: %d\n", ++CAS, ans);}
}
这篇关于3263 丽娃河的狼人传说的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
