当前位置 博文首页 > Keven_11的博客:C++题解:序列
?????目录
题目?
题解
- ?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题解:
知识点:贪心
分析:把所有区间按右端点排序,遍历每个区间,如果当前区间内的数不够,就从后往前增加数,这样可以更后面的区间尽可能地重叠。
代码:
cs#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; }