1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // 存储区间信息:l-区间左端点,r-区间右端点,c-该区间需要选的最少数字数量 struct node{ int l,r,c; }arr[1100]; // 比较函数:按区间右端点r升序排序,贪心策略优先处理右端点小的区间 bool cmp(node x,node y){ return x.r < y.r; } int main(){ int n; cin >> n; // [1] 输入区间个数n // [2] 输入每个区间的左端点、右端点和需要选的数量 for(int i = 0; i < n; i++) cin >> arr[i].l >> arr[i].r >> arr[i].c; bool brr[10000] = {false}; // 标记数组,记录数字是否已被选中,初始化为false sort(arr, arr + n, cmp); // [3] 按区间右端点升序排序 int sum = 0; // 记录总共选中的数字数量 // [4] 遍历每个区间,处理选数需求 for(int i = 0; i < n; i++){ // 先统计当前区间内已选中的数字,减少需要新增的选数数量 for(int j = arr[i].l; j <= arr[i].r; j++) if(brr[j]) arr[i].c--; // 从区间右端往左选未被选中的数字,尽可能复用后续区间的数字(贪心策略) for(int j = arr[i].r; j >= arr[i].l && arr[i].c > 0; j--){ if(brr[j] == false){ brr[j] = true; // 标记该数字已选 arr[i].c--; sum++; } } } cout << sum; // [5] 输出最少需要选中的数字总数 return 0; }
- 1
信息
- ID
- 1038
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者