糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

POJ 1230 Pass-Muraille 贪心

思路:

考虑最左边的需要移除墙的列。这列是必定要移除一些墙的。
不妨移除右边界较大的那些墙。

实现的时候,可以用基数排序的方式来找到右边界较大的墙。
开两个数组如下:
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, 
0sizeof(map));
        memset(cnt, 
0sizeof(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;
}

posted on 2010-05-24 23:20 糯米 阅读(841) 评论(0)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理