Intervals
题目描述
题目大意
其实这题目的大概意思是首先我们可以输入三个数a,b,c这三个数其中的前两个是一个区间表示在这个区间当中有至少c个数，我们输入n次这样的三个数，最后求出在整个区间当中数的最小的个数是多少？
相似题
我认为这道题和种树差不多
思路（种树）
贪心，要种树种得少，就要使一棵树给多个区间使用，这样，尽量在重叠区间种树即可，而重叠位置一定是区间尾部。处理问题时，先按所有区间的结束位置从小到大排序，若结束位置相同，则按开始位置从大到小排序。之后依次处理每个区间，先在第一个区间尾部种满足要求的树，对下一个区间，看差多少棵就在该区间尾部种多少。
步骤：
①先按照b[]从小到大快排
②对每个区间依次处理
a.从前到后扫描这个区间，统计点的个数；
b.若没有超过要求的点数，则从该区间后向前扫描，添加覆盖点。
③输出ans
思路（Intervals）
对比种树我们不难得到这道题目的思路
和种树可以一样
代码（种树）
#include<iostream>
using namespace std;
struct line{int s,e,v;}a[5005],mid;
int n,m,used[30005]={0};
void qsort(int L,int r)//快排
{ int i=L,j=r;mid=a[(L+r)/2];
while(i<=j)
{ while(a[i].e<mid.e)i++;
while(a[j].e>mid.e)j--;
if(i<=j)swap(a[i++],a[j--]);
}
if(L<j)qsort(L,j);
if(i<r)qsort(i,r);
}
void Init()
{ int i;
cin>>n>>m;
for(i=1;i<=m;i++)cin>>a[i].s>>a[i].e>>a[i].v;
qsort(1,m);
}
void Solve()
{ int i,j,k,ans=0;
for(i=1;i<=m;i++)//依次处理m个区间
{ k=0;
for(j=a[i].s;j<=a[i].e;j++)if(used[j])k++;//统计区间内已标记的数
if(k<a[i].v)
for(j=a[i].e;j>=a[i].s;j--)
if(!used[j]){used[j]=1;k++;ans++;if(k==a[i].v)break;}
}
cout<<ans<<endl;
}
int main()
{ Init();
Solve();
}代码（Intervals）
#include <bits/stdc++.h>
using namespace std;
struct node{
int l,r,w;
}e[50010];
int n,ans;
int vis[50010];
bool cmp(node x,node y){
return x.r<y.r;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].w);
sort(e+1,e+n+1,cmp);
for(int i=1;i<=n;i++){
int sum=0;
for(int j=e[i].l;j<=e[i].r;j++)
if(vis[j])sum++;
if(sum>=e[i].w)continue;
for(int j=e[i].r;j>=e[i].l;j--){
if(!vis[j])vis[j]=1,sum++,ans++;
if(sum>=e[i].w)break;
}
}
printf("%d",ans);
return 0;
}