1 条题解

  • 0
    @ 2026-2-1 16:03:28
    #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
    上传者