说明

该代码解决的问题是：给定一个由多个水平墙壁组成的舞台，以及一个最多能穿越 k 道墙壁的表演者，要求移除最少数量的墙壁，使得表演者从任意一列的上方开始向下移动时，穿过的墙壁数量不超过 k。如果某一列的墙壁数量超过 k，则需要移除部分墙壁以满足条件。

算法标签

• 贪心算法
• 区间处理
• 排序

解题思路

1. 输入处理：读取测试用例的数量 t，然后逐个处理每个测试用例。每个测试用例包含墙壁数量 n 和最大可穿越墙壁数 k，以及每道墙壁的两个端点坐标。
2. 墙壁预处理：确保每道墙壁的起点坐标 x1 小于终点坐标 x2（即水平墙壁从左到右）。
3. 统计墙壁覆盖：使用数组 a 统计每一列被多少道墙壁覆盖。同时记录最右侧的墙壁终点 maxwall。
4. 排序墙壁：根据墙壁的起点坐标 x1 对所有墙壁进行排序，以便后续处理。
5. 贪心移除墙壁：遍历每一列，如果某一列的墙壁数量超过 k，则选择覆盖该列且右端点最远的墙壁进行移除（贪心策略），以减少后续列的超限可能性。移除墙壁后更新统计数组 a。
6. 输出结果：统计并输出需要移除的墙壁数量。

分析

• 贪心策略：选择覆盖当前列且右端点最远的墙壁进行移除，是为了最大化减少后续列的墙壁覆盖数量。这种策略能够最小化需要移除的墙壁总数。
• 时间复杂度：对于每个测试用例，最坏情况下需要遍历所有列（最多100列）和所有墙壁（最多100道），因此时间复杂度为 O(t * n * maxwall)，在题目给定的约束下是可接受的。
• 正确性：通过贪心选择右端点最远的墙壁进行移除，确保了每次移除操作对后续列的优化效果最大，从而保证了最终结果的正确性。

实现步骤

1. 读取输入：读取测试用例的数量 t，然后逐个处理每个测试用例。
2. 初始化：初始化统计数组 a 和 maxwall。
3. 墙壁预处理：确保每道墙壁的起点坐标 x1 小于终点坐标 x2，并统计每一列的墙壁覆盖数量。
4. 排序墙壁：根据墙壁的起点坐标 x1 进行排序。
5. 贪心移除墙壁：遍历每一列，若当前列的墙壁数量超过 k，则选择覆盖该列且右端点最远的墙壁进行移除，并更新统计数组 a。
6. 输出结果：统计并输出需要移除的墙壁数量。

代码

#include<iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
//和上一题蛮像的,要先排序再搞,还有就是删区间的时候找最能靠右的删
using namespace std;
const int N=110;
struct node{
    int x1,y1,x2,y2;
}p[N];
bool cmp(node a,node b){
    return a.x1<b.x1;
}
int n,k,a[N];
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>k;
        memset(a,0,sizeof(a));
        int maxwall=-1;
        for(int i=0;i<n;i++){
            scanf("%d%d%d%d",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2);
            if(p[i].x1>p[i].x2)swap(p[i].x1,p[i].x2);
            for(int j=p[i].x1;j<=p[i].x2;j++)a[j]++;
            maxwall=max(maxwall,p[i].x2);
        }
        sort(p,p+n,cmp);
        int ans=0;
        for(int i=0;i<=maxwall;i++){//maxwall,,,,
            while(a[i]>k){
                ans++;
                int mx=-1,pos;
                for(int j=0;j<n;j++){
                    if(p[j].x1<=i && p[j].x2>=i && mx<p[j].x2)
                        pos=j,mx=p[j].x2;
                }
                for(int j=p[pos].x1;j<=p[pos].x2;j++)
                    a[j]--;
                p[pos].x1=p[pos].x2=-1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}