EOJ 3263 丽娃河的狼人传说(贪心)

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 。

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 华东师范大学网赛

point:

把右端点从小到大排列。然后每次尽量放右边。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>using namespace std;
struct node
{int l,r,x;
}b[1020];
bool cmd (node a,node c)
{return a.r<c.r;
}int main()
{int T;scanf("%d",&T);int p=0;while(T--){p++;int vis[1200];memset(vis,0,sizeof vis);int n,m,k;scanf("%d %d %d",&n,&m,&k);for(int i=1;i<=k;i++){int a;scanf("%d",&a);vis[a]=1;}int flag=0;for(int i=1;i<=m;i++){scanf("%d %d %d",&b[i].l,&b[i].r,&b[i].x);if(b[i].r-b[i].l+1<b[i].x){flag=1;}}if(flag){printf("Case %d: -1\n",p);continue;}sort(b+1,b+1+m,cmd);int ans=0;for(int i=1;i<=m;i++){int now=0;for(int j=b[i].l;j<=b[i].r;j++){if(vis[j]==1) now++;}if(now>=b[i].x) continue;else{int r=b[i].r;while(now<b[i].x){if(vis[r]==1){r--;continue;}else{vis[r]=1;r--;ans++;now++;}}}}printf("Case %d: %d\n",p,ans);}}