思路:
考虑最左边的需要移除墙的列。这列是必定要移除一些墙的。
不妨移除右边界较大的那些墙。
实现的时候,可以用基数排序的方式来找到右边界较大的墙。
开两个数组如下:
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;
}