本文主要是介绍ECNU 3263 丽娃河的狼人传说(华东师范大学邀请赛） （贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.ecnu.edu.cn/problem/3263/
丽娃河的狼人传说
Time limit per test: 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
解题思路：
按照右端点 来排序； 然后 扫描区间内 已有的 用需要的数目减去已有的数目，并把此时需要的 标记为存在
#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#include <stack>
#include <algorithm>
#include <stdio.h>
#include <cmath>using namespace std;
typedef long long ll;
const int MAXN=10005;
struct light{int left;int right;int need;
}node[MAXN];int cmp(light a,light b)
{if(a.right==b.right)return a.left<b.left;return a.right<b.right;
}int main()
{int i,j,cont=0;int x,T;int n,m,k;int vis[MAXN];cin>>T;while(T--){cin>>n>>m>>k;int ans=0;memset(vis,0,sizeof(vis));memset(node,0,sizeof(node));for(i=0;i<k;i++){cin>>x;vis[x]=1;}for(i=0;i<m;i++){cin>>node[i].left>>node[i].right>>node[i].need;}sort(node,node+m,cmp);for(i=0;i<m;i++){if((node[i].right-node[i].left+1)<node[i].need){ans=-1;break;}else{int temp=0;for(j=node[i].left;j<=node[i].right;j++){if(vis[j])temp++;}if(temp<node[i].need){ans+=node[i].need-temp;// 需要在添加路灯个数}temp=node[i].need-temp;// 把添加的路灯 设置为 已访问for(j=node[i].right;j>=node[i].left&&temp>0;j--){if(!vis[j]){vis[j]=1;temp--;}} }}printf("Case %d: %d\n",++cont,ans);}return 0;
}
这篇关于ECNU 3263 丽娃河的狼人传说(华东师范大学邀请赛） （贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
