53 lines
1.5 KiB
C++
53 lines
1.5 KiB
C++
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 3e4 + 10;
|
|
int n; // 共n个区间
|
|
int st[N]; // 哪些数字已经被使用过了
|
|
int ans; // 答案
|
|
|
|
// 区间，一般用结构体来存储
|
|
struct Node {
|
|
int l, r; // 左端点，右端点
|
|
int c; // 存在的数字个数
|
|
} a[N];
|
|
|
|
int cmp(Node a, Node b) {
|
|
return a.r < b.r; // 按右端点排序
|
|
}
|
|
|
|
int main() {
|
|
cin >> n;
|
|
for (int i = 1; i <= n; i++)
|
|
cin >> a[i].l >> a[i].r >> a[i].c;
|
|
|
|
// 按右端点排序
|
|
sort(a + 1, a + 1 + n, cmp);
|
|
|
|
for (int i = 1; i <= n; i++) { // 遍历每个区间
|
|
|
|
// 我们准备从右向左进行有效点覆盖，但这里有问题，因为前面可能已经消耗掉一些点了，我们需要知道前面消耗了多少个点
|
|
int cnt = 0;
|
|
for (int j = a[i].l; j <= a[i].r; j++) {
|
|
if (st[j])
|
|
cnt++;
|
|
}
|
|
// 如果还有剩余的数字可以用
|
|
if (cnt < a[i].c) {
|
|
for (int j = a[i].r;; j--) { // 从右向左去用
|
|
if (!st[j]) { // 如果这个位置没有被使用过，那么就使用上
|
|
cnt++; // 记录本区间使了多少个数字
|
|
st[j] = 1; // 标识使用过了
|
|
// ans++;
|
|
}
|
|
if (cnt == a[i].c) // 如果使没了，就停止
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
// 遍历一遍数组，找出答案数量
|
|
for (int i = 0; i < N; i++)
|
|
ans += st[i];
|
|
// 输出答案
|
|
cout << ans << endl;
|
|
return 0;
|
|
} |