糯米

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

POJ 1231 The Alphabet Game 贪心

近来实验室给派了新活,跟原来做的东西,以及我们熟悉的东西都比较不搭边的,郁闷。
折腾了两个星期,昨天终于有了些进展。
今天做了两道水题~  都是贪心


思路:
这题看上去挺唬人,提交的人也不多,实际上都是水题来的。
1. 对于同一种字母,求出它出现位置的最左边、最右边、最上边、最下边。这就构成了一个矩形。
2. 对于在x轴上投影重合的一系列矩形,他们必定处在同一个方格内。给这些方格编号。
3. 对于在y轴上投影重合的一系列矩形,如果其中两个编号相同,就不符合条件了。

#include <stdio.h>
#include 
<stdlib.h>
#include 
<algorithm>

using namespace std;

struct rect {
    
int left, right, top, bottom;
    
int rank_x;
}
 rec[32];
int T, K, P;

int cmp_x(const void *a, const void *b)
{
    
return ((struct rect *)a)->left - ((struct rect *)b)->left;
}


int cmp_y(const void *a, const void *b)
{
    
return ((struct rect *)a)->top - ((struct rect *)b)->top;
}


inline 
int solve()
{
    
int i, last, rank, mask;

    qsort(rec, K, 
sizeof(rec[0]), cmp_x);
    rank 
= 0;
    
for (i = 0; i < K; ) {
        last 
= rec[i].right;
        
while (i < K && rec[i].left <= last) {
            rec[i].rank_x 
= rank;
            last 
= max(last, rec[i].right);
            i
++;
        }

        rank
++;
    }


    qsort(rec, K, 
sizeof(rec[0]), cmp_y);
    
for (i = 0; i < K; ) {
        mask 
= 0;
        last 
= rec[i].bottom;
        
while (i < K && rec[i].top <= last) {
            
if (mask & (1 << rec[i].rank_x))
                
return 0;
            mask 
|= 1 << rec[i].rank_x;
            last 
= max(last, rec[i].bottom);
            i
++;
        }

    }


    
return 1;
}


int main()
{
    
int i, j, x, y;

    scanf(
"%d"&T);
    
while (T--{
        scanf(
"%d%d"&K, &P);
        
for (i = 0; i < K; i++{
            rec[i].left 
= rec[i].top = 1000000;
            rec[i].right 
= rec[i].bottom = 0;
            
for (j = 0; j < P; j++{
                scanf(
"%d%d"&x, &y);
                
if (x < rec[i].left)
                    rec[i].left 
= x;
                
if (x > rec[i].right)
                    rec[i].right 
= x;
                
if (y < rec[i].top)
                    rec[i].top 
= y;
                
if (y > rec[i].bottom)
                    rec[i].bottom 
= y;
            }

        }

        printf(
"%s\n", solve() ? "YES" : "NO");
    }


    
return 0;
}


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


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