解題思路：這道題目是用貪心的思想，從左向右掃描場地的每一列是否合法。若不合法，貪心的找出從該列起向右延伸最長的m道墻，移除這m道墻使得該列合法。

我最開始代碼會出現(xiàn)這樣的問題：如果兩個墻是連在一起的，那么會被當(dāng)做一個墻來處理。。。

AC:

#include <iostream> #include<cstdio> #include<cstring> using namespace std; const int White = 0; int n, k; int w, h; short g[101][101];int Greedy() {int minCount = 0;for( int c = 0; c <= w; ++ c ) {// 掃描每一行,找出墻數(shù)numint num = 0;for( int r = 0; r <= h; ++ r )if( g[r][c] != White )++ num;// 移除多余墻while( num > k ) {// 找出所有墻中右端點(diǎn)最大的索引int ind = -1, maxCount = 0;for(int r = 0; r <= h; ++r)if( g[r][c] != White ) {int cc = c + 1, count = 0;while( g[r][cc++] == g[r][c] ) ++ count;if( count > maxCount ) {maxCount = count;ind = r;}}for( int cc = c; cc <= c + maxCount; ++ cc ) g[ind][cc] = White;-- num;++ minCount;}}return minCount; }int main() {int T;scanf("%d",&T);while( T -- ) {memset( g, White, sizeof(g) );scanf( "%d%d", & n, & k );for( int i = 0; i < n; ++ i ) {int bx, by, ex, ey;scanf( "%d%d%d%d", & bx, & by, & ex, & ey );if( bx > ex ) ::swap( bx, ex );if( ex > w ) w = ex;if( ey > h ) h = ey;for( int c = bx; c <= ex; ++ c )g[by][c] = i + 1;}printf("%d\n",Greedy());}return 0; }

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的poj 1230（贪心）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。