#牛客网 监视任务（贪心 + 线段树）

 

题目描述

𝑅𝑒𝑘𝑖在课余会接受一些民间的鹰眼类委托，即远距离的狙击监视防卫。 𝑅𝑒𝑘𝑖一共接到了𝑚份委托，这些委托与𝑛个直线排布的监视点相关。 第𝑖份委托的内容为：对于区间[𝑙𝑖, 𝑟𝑖]中的监视点，至少要防卫其中的𝑘𝑖个。 𝑅𝑒𝑘𝑖必须完成全部委托，并且希望选取尽量少的监视点来防卫。

输入描述:

第一行，两个正整数𝑛，𝑚。 接下来𝑚行，每行三个整数𝑙𝑖，𝑟𝑖，𝑘𝑖。

输出描述:

一行，一个整数，即所需防卫的最少监视点数量。

示例1

输入

 

11 5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1

输出

 

6

备注:

对于10%的数据，𝑛 ≤ 10。 对于20%的数据，𝑛 ≤ 20。 对于30%的数据，𝑛,𝑚 ≤ 30。 对于60%的数据，𝑛,𝑚 ≤ 1000。 对于100%的数据，𝑛 ≤ 500000，𝑚 ≤ 1000000，𝑙𝑖 ≤ 𝑟𝑖，𝑘𝑖 ≤ 𝑟𝑖−𝑙𝑖+1。

题目大意 ： 有一条包含N个点的线段， M个限制条件， 每个条件表示从L到R上至少需要放几个点，输出整个线段至少放几个点才能满足要求

思路 ： 贪心思想，将限制条件按照右端点小的依次排序， 不难想到，每次先查询该区间的点数是否已经满足条件，如果不满足，看还差多少，将差值尽量靠右放，途中注意已经放过点的地方，线段树维护区间和，最后输出即可

Accepted code

#include<bits/stdc++.h> #include<unordered_map> using namespace std; #define sc scanf #define ls rt << 1 #define rs ls | 1 #define Min(x, y) x = min(x, y) #define Max(x, y) x = max(x, y) #define ALL(x) (x).begin(),(x).end() #define SZ(x) ((int)(x).size()) #define MEM(x, b) memset(x, b, sizeof(x)) #define lowbit(x) ((x) & -(x)) #define P2(x) ((x) * (x)) typedef long long ll; const int MOD = 1e9 + 7; const int MAXN = 1e6 + 100; const int INF = 0x3f3f3f3f; inline ll fpow(ll a, ll b){ ll r = 1, t = a; while (b){ if (b & 1)r = (r*t) % MOD; b >>= 1; t = (t*t) % MOD; }return r; } struct Tree { int l, r, ans, len, lzy; }t[MAXN * 4]; struct node { int l, r, w; }p[MAXN]; bool cmp(node a, node b) { return a.r < b.r; } int n, m, scnt; void Build(int rt, int l, int r) { t[rt].l = l, t[rt].r = r; t[rt].len = r - l + 1; if (l == r) return; int mid = (l + r) >> 1; Build(ls, l, mid); Build(rs, mid + 1, r); } void Pushdown(int rt) { t[ls].lzy = t[rs].lzy = 1; t[ls].ans = t[ls].len, t[rs].ans = t[rs].len; t[rt].lzy = 0; } void Update(int rt, int l, int r) { if (scnt == 0) return; // 放完退出 if (t[rt].l >= l && t[rt].r <= r && t[rt].len <= scnt) { // 往下走 int tmp = t[rt].len - t[rt].ans; scnt -= tmp; t[rt].ans = t[rt].len, t[rt].lzy = 1; // 更新状态 return; } int mid = (t[rt].l + t[rt].r) >> 1; if (t[rt].lzy) Pushdown(rt); if (mid < r) Update(rs, l, r); if (mid >= l) Update(ls, l, r); t[rt].ans = t[ls].ans + t[rs].ans; } int Query(int rt, int l, int r) { if (t[rt].l >= l && t[rt].r <= r) return t[rt].ans; int mid = (t[rt].l + t[rt].r) >> 1, ui = 0, vi = 0; if (t[rt].lzy) Pushdown(rt); if (mid >= l) ui = Query(ls, l, r); if (mid < r) vi = Query(rs, l, r); return ui + vi; } int main() { cin >> n >> m; Build(1, 1, n); for (int i = 0; i < m; i++) sc("%d %d %d", &p[i].l, &p[i].r, &p[i].w); sort(p, p + m, cmp); for (int i = 0; i < m; i++) { int ui = p[i].l, vi = p[i].r, wi = p[i].w; int ans = Query(1, ui, vi); if (ans < wi) { scnt = wi - ans; Update(1, ui, vi); } } cout << Query(1, 1, n) << endl; return 0; }