POJ 1230 Pass-Muraille （贪心）

题目链接：

POJ 1230

题目大意：

舞台上有n堵墙，每堵墙都是平行于x轴，魔术师每次表演可以在观众指定的某一列中穿过k堵墙，为了保证魔术成功，魔术师需要拆掉舞台上的一些墙，问最少拆掉多少堵可以使魔术成功。

题解：

用一个二维数组wall[i][j]存墙的信息, wall[i][j]表示在第i行第j列的墙的右坐标。wall[i][1001]表示这一列有多少堵墙，从左到右遍历数组，一旦超过k，那么就选择向右伸展最长的墙拆掉，因为拆掉所有墙的代价一样，所以拆的墙越长越好，而且不需要管前面合格的列的情况，因为对后面没有影响。

坑点：

左右坐标的位置可能互换，也就是说右坐标的x值比左坐标的值要小。

AC代码：

// // main.cpp // POJ 1230 // // Created by izayoi on 2017/3/8. // Copyright © 2017年 izayoi. All rights reserved. // #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn = 1005; int numb[maxn][maxn]; int main(int argc, const char * argv[]) { int t; scanf("%d",&t); while(t--) { int n,k; scanf("%d%d", &n, &k); memset(numb,0,sizeof(numb)); int x1,y1,x2,y2; int maxr = 0; for(int i = 0; i < n; i++) { scanf("%d%d%d%d", &x1, &y1, &x2, &y2); if(x1 > x2)swap(x1, x2); for(int j = x1; j <= x2; j++) { numb[j][1001]++; numb[j][y1] = max(numb[j][y1],x2); } maxr = max(x2,maxr); } int cnt = 0; for(int i = 0; i <= maxr; i++) { while(numb[i][1001] > k) { int maxl = 0, maxy = 0; for(int j = 0; j < 105; j++) { if(numb[i][j] > maxl) { maxl = numb[i][j]; maxy = j; } } for(int j = i; j <= maxl; j++) { numb[j][1001]--; numb[j][maxy] = 0; } cnt++; } } printf("%d\n", cnt); } return 0; } /* 9 3 1 2 0 4 0 0 1 1 1 1 2 2 2 7 3 0 0 3 0 6 1 8 1 2 3 6 3 4 4 6 4 0 5 1 5 5 6 7 6 1 7 3 7 7 2 1 0 7 0 2 1 10 1 9 2 12 2 4 3 12 3 3 4 8 4 5 5 6 5 10 6 11 6 4 1 0 3 9 3 0 0 3 0 4 0 7 0 3 2 6 2 3 0 3 0 0 0 6 1 8 1 2 3 6 3 7 3 3 0 0 0 6 1 8 1 2 3 6 3 4 4 6 4 0 5 1 5 5 6 7 6 1 7 3 7 8 2 0 0 0 0 0 1 0 1 5 0 5 0 5 1 5 1 1 1 4 1 0 2 2 2 3 2 5 2 1 3 4 3 3 1 2 0 4 0 0 1 1 1 1 2 2 2 8 2 0 0 0 0 0 1 0 1 5 0 5 0 5 1 5 1 1 1 4 1 0 2 2 2 3 2 5 2 4 3 1 3 ans 1 1 3 2 3 1 2 1 2 */