\(这道题想了很久......菜是原罪啊\)
\(大概思路是先把所有区间的点染色一遍\)
\(然后一个点一个点判断,如果不符合题意就删去一条覆盖这个点的线段\)
\(删去哪一个呢?当然是删掉区间右端点最右边的那个。因为前面的点不用管了,已经符合要求\)
\(然后如果能覆盖到后面的点,那么对答案是不利的,应该删去\)
\(至于我的代码可能有点难以理解,大概意思是先算出要保存的线段。一旦不符合就删掉前面选过的线段中右端点最远的线段删去\)
#include <bits/stdc++.h>
using namespace std;
int vis[209],l[209],r[209],used[209],ans[209],top;
int n,k;
struct p{
int l,r,num;
bool operator < (const p&tmp) const{
if(this->l==tmp.l) return this->r<tmp.r;
return this->l<tmp.l;
}
}a[209];
bool isok(int num)
{
for(int i=a[num].l;i<=a[num].r;i++)
if(vis[i]+1>k) return false;
used[num]=1;//标记使用
for(int i=a[num].l;i<=a[num].r;i++) vis[i]++;//染色
return true;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i].l>>a[i].r,a[i].num=i;
sort(a+1,a+1+n);
for(int i=a[1].l;i<=a[1].r;i++) vis[i]++;
int xu=1;used[1]=1;
for(int i=2;i<=n;i++)
{
int flag=1;
if(isok(i))
{
if(a[i].r>=a[xu].r) xu=i;
}
else//放不下
{
if(a[i].r>a[xu].r) continue;
used[xu]=0,used[i]=1;
for(int j=a[xu].l;j<=a[xu].r;j++) vis[j]--;
for(int j=a[i].l;j<=a[i].r;j++) vis[j]++;
int maxx=0;
for(int j=1;j<=n;j++)
if(used[j]==0) continue;
else if(a[j].r>=maxx) maxx=a[j].r,xu=j;
}
}
for(int i=1;i<=n;i++)
{
if(used[i]) continue;
ans[++top]=a[i].num;
}
sort(ans+1,ans+1+top);
cout<<top<<endl;
for(int i=1;i<=top;i++) cout<<ans[i]<<" ";
}