题目链接：https://vjudge.net/contest/338207#problem/G 翻译： 输入一个n和k，接下来输入n条线段的左右端点。对于每条线段，覆盖这条线段上的所有整数点(如1 3这条线段则覆盖1 2 3这三个点)。 求最少删去几条线段，保证每个点覆盖的次数不大于k。先输出删除边的个数，接着输出边的编号。 分析：此题n的范围有两个， (1≤k≤n≤200) (1≤k≤n≤2⋅10^5),对于n较小的范围，可以用差分数组记录每个点被覆盖了多少次。接着遍历所有的点，找被覆盖次数大于k的点，接着遍历n条线段，找到这个点所处的线段，并找到右端点最大的那个线段，进行去除。 代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=300; int n,k,d[N]; struct node { int u,v; } s[N]; int main() { while(~scanf("%d%d",&n,&k)) { memset(d,0,sizeof(d)); int mx=-1; for(int i=1; i<=n; i++)/*差分数组*/ { scanf("%d %d",&s[i].u,&s[i].v); mx=max(mx,s[i].u); mx=max(mx,s[i].v); d[s[i].u]++; d[s[i].v+1]--; } for(int i=1; i<=mx; i++) d[i]+=d[i-1]; /*求出每个点被覆盖的几次*/ int book[N]; memset(book,0,sizeof(book)); int flag=0; for(int j=1; j<=mx; j++) { while(d[j]>k) /*找到一个点i被覆盖的次数大于k*/ { flag=1; int tab=0; for(int i=1; i<=n; i++)/*从n条边中找到i所处的线段，并在所有的线段中找到最右边最大的那个线段*/ { if(book[i]==0&&s[i].u<=j&&j<=s[i].v&&(tab==0||s[i].v>s[tab].v)) tab=i; } if(tab==0)break;/*保证去除的边最少,因为边可能重合,所以标记*/ for(int i=s[tab].u; i<=s[tab].v; i++) d[i]--; book[tab]=1; } } if(flag==0) printf("0\n"); else { int num=0; for(int i=1; i<=n; i++) { if(book[i]) num++; } printf("%d\n",num); for(int i=1; i<=n; i++) if(book[i]) printf("%d ",i); printf("\n"); } } return 0; }对于n的数据加强，再采用上述方法就不行，需要用容器进行维护。 代码：
#include<cstdio> #include<cstring> #include<vector> #include<set> #include<algorithm> using namespace std; const int N=2*1e5+10; struct node { int id; int r; }; bool operator <(node u,node v) { //总的思想:对于一个点若覆盖超过k次,则删除右端点最大的边 if(u.r!=v.r) return u.r<v.r;/*右端点从小到大排序*/ else return u.id<v.id;/*下标从小到大排序*/ } vector<node>v[N];/*vector容器里面存放的是结构体,开了一个v[N]的数组,相当于二维数组*/ vector<int>ans; int main() { int n,k; scanf("%d%d",&n,&k); for(int i=1; i<=n; i++) { node q; int x,y; scanf("%d%d",&x,&y); q.id=i; q.r=y; v[x].push_back(q);/*记录所有以x为左端点的线段*/ } set<node>s; for(int i=1; i<N; i++) { while(s.size()&&(*s.begin()).r<i)/*刚开始是不执行while循环的,若set容器中存的线段的右端点小于下一个点,那么这条边就可以删去,此处的操作是核心*/ s.erase(*s.begin()); for(int j=0; j<v[i].size(); j++) /*遍历以顶点i为左端点的所有的线段*/ s.insert(v[i][j]);/*set容器中存的是这条线段的所有信息,set容器插入元素时,会自动调整二叉树的结构,此时的‘<’的重载操作就起作用*/ while(s.size()>k) { ans.push_back((*s.rbegin()).id); s.erase(*s.rbegin()); } } printf("%d\n",ans.size()); for(int i=0; i<ans.size(); i++) printf("%d ",ans[i]); return 0; }最好的十年
