思路:
考虑最左边的需要移除墙的列。这列是必定要移除一些墙的。
不妨移除右边界较大的那些墙。
实现的时候,可以用基数排序的方式来找到右边界较大的墙。
开两个数组如下:
map[i][j] = { 第i列中,从该列开始向右延伸,长度为j的墙的数目}
cnt[i] = {第i列中墙的数目}
这样代码比较方便,速度也快。
#include <stdio.h>
#include <string.h>

int T, N, K;
char map[128][128];
int cnt[128];

int main()


{
int x1, x2, y;
int i, j, i2, j2, ans;

scanf("%d", &T);

while (T--)
{
scanf("%d%d", &N, &K);
memset(map, 0, sizeof(map));
memset(cnt, 0, sizeof(cnt));

while (N--)
{
scanf("%d%d%d%d", &x1, &y, &x2, &y);

if (x1 > x2)
{
x1 ^= x2;
x2 ^= x1;
x1 ^= x2;
}

for (i = x1; i <= x2; i++)
{
map[i][x2 - i + 1]++;
cnt[i]++;
}
}
ans = 0;

for (i = 0; i <= 100; i++)
{
if (cnt[i] <= K)
continue;

for (j = 100; cnt[i] > K && j > 0; j--)
{

while (cnt[i] > K && map[i][j])
{
i2 = i;
j2 = j;

while (j2)
{
map[i2][j2]--;
cnt[i2]--;
j2--;
i2++;
}
ans++;
}
}
}
printf("%d\n", ans);
}

return 0;
}
