UVa 11134 Fabled Rooks （贪心+问题分解）

题意：在一个n*n的棋盘上放n个车，让它们不互相攻击，并且第i辆车在给定的小矩形内。

析：说实话，一看这个题真是没思路，后来看了分析，原来这个列和行是没有任何关系的，我们可以分开看，

把它变成两个一维问题，也就是说，我们可以把行看成是1-n，然后把x1-x2看成小区间，这样的话，

是不是就感觉简单的了，还有好几坑，被坑的惨惨的。

首先对行排序，按照每个右端点排，然后扫一遍，去找左端点，找到就立马选上（贪心），并且是一定满足的，

如果找不到，就退出，说明没有解。同理列也是这样。

后来看了Rujia Liu的代码，那叫一个精简啊，连结构体都没用，真是大神啊。

我的代码如下：

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int maxn = 5000 + 10;

struct node{

    int x1, x2, y1, y2;

    int x, y, id;

    bool usedx, usedy;

};

node a[maxn];

bool cmp1(const node &p, const node &q){  return p.x2 < q.x2; }

bool cmp2(const node &p, const node &q){  return p.y2 < q.y2; }

bool cmp3(const node &p, const node &q){  return p.id < q.id; }

int main(){

    int n;

    while(scanf("%d", &n) && n){

        for(int i = 0; i < n; ++i){

            scanf("%d %d %d %d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);

            a[i].usedx = a[i].usedy = false;

            a[i].id = i;

        }

        sort(a, a+n, cmp1);

        bool ok;

        for(int i = 0; i < n; ++i){

            ok = false;

            for(int j = 0; j < n; ++j){

                if(!a[j].usedx && a[j].x1 <= i+1){

                    if(a[j].x2 <= i)   break;

                    a[j].x = i+1;

                    a[j].usedx = true;

                    ok = true;

                    break;

                }

            }

            if(!ok)  break;

        }

        if(!ok){  printf("IMPOSSIBLE\n");  continue;  }

//        puts("++++");

        sort(a, a+n, cmp2);

        for(int i = 0; i < n; ++i){

            ok = false;

            for(int j = 0; j < n; ++j){

                if(!a[j].usedy && a[j].y1 <= i+1){

                    if(a[j].y2 <= i)   break;

                    a[j].y = i+1;

                    a[j].usedy = true;

                    ok = true;

                    break;

                }

            }

            if(!ok)  break;

        }

        if(!ok){  printf("IMPOSSIBLE\n");  continue;  }

        sort(a, a+n, cmp3);

        for(int i = 0; i < n; ++i)

            printf("%d %d\n", a[i].x, a[i].y);

    }

    return 0;

}

下面是Rujai Liu的代码真是膜拜啊：

#include<cstdio>

#include<cstring>

#include <algorithm>

using namespace std;

bool solve(int *a, int *b, int *c, int n) {

  fill(c, c+n, -1);

  for(int col = 1; col <= n; col++) {

    int rook = -1, minb = n+1;

    for(int i = 0; i < n; i++)

      if(c[i] < 0 && b[i] < minb && col >= a[i]) { rook = i; minb = b[i]; }

    if(rook < 0 || col > minb) return false;

    c[rook] = col;

  }

  return true;

}

const int maxn = 5000 + 5;

int n, x1[maxn], yy1[maxn], x2[maxn], y2[maxn], x[maxn], y[maxn];

int main() {

  while(scanf("%d", &n) == 1 && n) {

    for (int i = 0; i < n; i++)

      scanf("%d%d%d%d", &x1[i], &yy1[i], &x2[i], &y2[i]);

    if(solve(x1, x2, x, n) && solve(yy1, y2, y, n))

      for (int i = 0; i < n; i++) printf("%d %d\n", x[i], y[i]);

    else

      printf("IMPOSSIBLE\n");

  }

  return 0;

}

巴特西

UVa 11134 Fabled Rooks （贪心+问题分解）

最新文章

热门文章