挺简单的算法我没想出来..

考虑最左边的需要移除墙的列。这列是必定要移除一些墙的。
不妨移除右边界较大的那些墙。
实现的时候，可以用基数排序的方式来找到右边界较大的墙。
开两个数组如下：
map[i][j] = { 第i列中，从该列开始向右延伸，长度为j的墙的数目}
cnt[i] = {第i列中墙的数目}
这样代码比较方便，速度也快。          ——荣誉属于糯米

糯米的这个数据结构非常棒, 我做了一点改进: 糯米记录了右边还有多长的墙, 实际上只要记录右边墙的边界就可以了, 省掉一些计算和思维复杂度
所以我的代码精简一点, 看我的吧 🙂

这种题一眼看上去像DP, 我看了点东西说DP和贪心有很多相似之处, 比如都是找最优子结构. 区别在于贪心从最优子结构里选出一个或几个就行. 具体有什么区别也没太搞清楚, 感觉DP有一个图的延伸, 每个状态都可能被多次使用, 而贪心不会.

代码点下面:

#include <stdio.h>
#include <string.h>

int main () {
    int t;
    scanf("%d",&t);
    while(t--) {
        int N,K;
        scanf("%d%d",&N,&K);

        int a[101][101],k[101];
        memset(a,0x00,sizeof(a));
        memset(k,0x00,sizeof(k));
        for(int i=1;i<=N;i++) {
            int x0,y,x1;
            scanf("%d%d%d%d",&x0,&y,&x1,&y);
            if(x0>x1) {
                x0^=x1;
                x1^=x0;
                x0^=x1;
            }
            for(int foo=x0;foo<=x1;foo++) {
                a[foo][x1]++;
                k[foo]++;
            }
        }

        int result=0;
        for(int i=0;i<=100;i++)
            while(k[i]>K) {
                int w;  //right edge of wall
                for(w=100;a[i][w]==0;w--);
                for(int j=i;j<=w;j++) {
                    a[j][w]--;
                    k[j]--;
                }
                result++;
            }

        printf("%d\n",result);
    }
    return 0;
}