受欢迎的昆明网站推广/长沙网站提升排名

题目链接
这道题感觉就是greedy的题。但是还是看了解题报告。知道做法后实现很简单，只需要注意测试数据中有左端点的x坐标大于右端点的x坐标的情况，调换下即可。

贪心的策略是按照x从左往右扫描，如果某一列(某一个x值)对应（被覆盖）的墙的个数cnt大于k，那么需要从这些墙中删掉cnt - k 个。删除的顺序是将墙按照右端点的x值从大到小的顺序排序，按顺序删除。

这样做的大致思路是因为对每个“覆盖墙”我们不用考虑其左端点（因为左边的所有列已经是满足条件的），右端点大的覆盖的右边的x多，所以先删除。这不是个证明。证明请参考其他资料。

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 105;
int lx[MAXN],ly[MAXN],rx[MAXN],ry[MAXN];
int wall[MAXN];
bool exist[MAXN];
int main()
{int T,cas;int n,k,i,j,p;int max_x;scanf("%d",&T);for (cas = 1; cas <= T; ++cas){memset(wall,0,sizeof(wall));max_x = 0;scanf("%d %d",&n,&k);for (i = 0; i < n; ++i){scanf("%d %d %d %d",&lx[i],&ly[i],&rx[i],&ry[i]);if (rx[i] < lx[i]){int tmp = lx[i];lx[i] = rx[i];rx[i] = tmp;}if (rx[i] > max_x)max_x = rx[i];for (j = lx[i]; j <= rx[i]; ++j)++wall[j];exist[i] = true;}int ans = 0;for (i = 0; i <= max_x; ++i){if (wall[i] <= k)continue;int chai = wall[i] - k;for (j = 0; j < chai; ++j){int cnt = -1;for (p = 0; p < n; ++p){if (lx[p] <= i && rx[p] >= i && (cnt == -1 || rx[p] > rx[cnt]) && exist[p] == true)cnt = p;}exist[cnt] = false;for (p = lx[cnt]; p <= rx[cnt]; ++p)--wall[p];}ans += chai;}printf("%d\n",ans);}return 0;
}