题解 P1645 【序列】
顾z
2018-06-28 06:53:07
"~~序列是不连续的~~"
“~~你们应该知道~~”
思想：sort排序：以左端点为第一关键字排序，右端点为第二关键字排序。
区间覆盖问题
做法：
每次选取左端点最大的进行贪心。
枚举这一段区间时，从左到右选取
尽可能靠左的整数点。
这时候要判断是否被标记过。
如果被标记过，该区间中的C（同题目）--。
再次遍历这段区间，要判断此时的C是否<=0.
如果<=0则要break；
如果存在C，则继续标记较靠左的整数点。
CODE如下： ~~貌似可以改一下 大佬手轻点~~
~~蒟蒻第一篇题解~~
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#define ll long long
#define ull unsigned long long
#define inf 2147483647
using namespace std;
int N,L,R,C,minl=9999,maxr,ans;bool NOW[20000];
struct code{
int l,r,c;
}op[20000];
bool read(int &x){
int f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
x*=f;
}
void print(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) print(x/10);
putchar(x%10+'0');
}
bool ccp(const code &a,const code &b)
{
if(a.l!=b.l)return a.l<b.l;
else return a.r>b.r;
}
int main()
{
read(N);
for(int i=1;i<=N;i++)
{
read(op[i].l),read(op[i].r),read(op[i].c);
minl=min(minl,op[i].l),maxr=max(op[i].r,maxr);
}
sort(op+1,op+N+1,ccp);
for(int i=N;i>=1;--i)
{
int couldget=op[i].c;
for(int k=op[i].l;k<=op[i].r;k++)if(NOW[k])couldget--;
for(int j=op[i].l;j<=op[i].c+op[i].l &&j<=op[i].r;j++)
{
if(couldget<=0)break;
else if(!NOW[j]){
couldget--;
NOW[j]=1;
}
}
}
for(int i=minl;i<=maxr;i++)
if(NOW[i])ans++;
print(ans);
}
```