当前位置 博文首页 > Keven_11的博客:C++题解:序列

    Keven_11的博客:C++题解:序列

    作者:[db:作者] 时间:2021-08-18 15:49

    ?????目录

    题目?

    题解


    题目?

    • ?1000ms
    • ?131072K

    有一个整数序列,它的每个数各不相同,我们不知道它的长度是多少(即整数个数),但我们知道在某些区间中间至少有多少个整数,用 (Li?,Ri?,Ci?)?来描述,表示这个整数序列中至少有?C_i??个数来自区间 [Li?,Ri?],给出若干个这样的区间,问这个整数序列的长度最少能为多少?

    输入格式

    第一行一个整数 N?(1≤N≤1000),表示区间个数;

    接下来?NN?行,每行三个整数Li?,Ri?,Ci??(1≤Li?≤Ri?≤1000,1≤Ci?≤Ri??Li?+1),描述一个区间和区间内数至少有?Ci??个。

    输出格式

    一个数,表示该整数序列的最小长度。

    输出时每行末尾的多余空格,不影响答案正确性

    要求使用「文件输入输出」的方式解题,输入文件为?seq.in,输出文件为?seq.out

    样例输入

    4
    4 5 1
    6 10 3
    7 10 3
    5 6 1

    样例输出

    4

    题解:

    知识点:贪心

    分析:把所有区间按右端点排序,遍历每个区间,如果当前区间内的数不够,就从后往前增加数,这样可以更后面的区间尽可能地重叠。

    代码:

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #define _for(i,a,b) for (int i=(a);i<=(b);i++)
    using namespace std;
    const int N=1e3+5;
    struct set{
        int l,r,c;//表示这序列中至少有 C个数来自区间 [L,R]
        bool operator<(const set &s)const{//重载运算符,按右端点排序
            return r<s.r;
        }
    }a[N];
    bool vis[N];//vis[i]表示第i位置有没有数
    int main(){
        freopen("seq.in","r",stdin);
        freopen("seq.out","w",stdout);
        int n,ans=0;//注意初始化
        scanf("%d",&n);
        _for(i,1,n){
            scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].c);
        }
        sort(a+1,a+n+1);//贪心,按右端点排序
        _for(i,1,n){
            int tot=0;//tot表示这个区间里已经有多少数。
            _for(j,a[i].l,a[i].r){
                if (vis[j]){
                    tot++;
                }
            }
            if (tot<a[i].c){//如果当前区间内的数不够
                for (int j=a[i].r;j>=a[i].l;j--){//就从后往前增加数,从前往后要不得
                    if (!vis[j]){//如果没有
                        tot++;
                        ans++;
                        vis[j]=true;
                        if (tot==a[i].c){//如果增加数到符合要求数量,退出
                            break;
                        }
                    }
                }
            }
        }
        printf("%d\n",ans);
        return 0;
    }

    cs