丽娃河的狼人传说

原题：丽娃河的狼人传说

原题大意

丽娃河可以看成是从 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

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

算法分析

按右端点排序，然后对于不满足条件的尽量往右垒就好了。贪心的证明：由于左边的都已经垒满了，所以垒左边的肯定是没意义的。垒中间肯定没有垒右边的号，因为右边的区间不可能长得断开，使得垒在左边收益更大。这样就可以实现 O(n2)。

程序代码

#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 1005;
int T, n, m, k, kase;
int line[maxn], cnt;
struct interval{
    int l, r, req;
    bool friend operator < (interval a, interval b){
        return a.r < b.r;
    }
}inter[maxn];
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    bool fg = false;
    while(T--){
        mem(line, 0);
        fg = true;
        cnt = 0;
        cin >> n >> m >> k;
        for(int i = 0; i < k; i++){
            int t;
            cin >> t;
            line[t]++; 
        }
        for(int i = 0; i < m; i++){
            cin >> inter[i].l >> inter[i].r >> inter[i].req;

        }
        sort(inter, inter+m);
        for(int i = 0; i < m; i++){
            int res = 0;
            for(int j = inter[i].l; j <= inter[i].r; j++)
                res+=line[j];
            int len = inter[i].r-inter[i].l+1;
            if(len - res  < inter[i].req - res){fg = false; break;}
            int t = inter[i].req - res;
            for(int j = inter[i].r; j >= inter[i].l && t > 0; j--){
                if(line[j] == 0){
                    line[j]++;
                    t--;
                    cnt++;
                }
            }
        }
        if(!fg) cnt = -1;
        cout << "Case " << ++kase << ": " << cnt << endl;
    }
    return 0;
}