UVa 11134 – Fabled Rooks [贪心]

Link

点击打开题目链接

Problem

We would like to place n rooks, 1 ≤ n ≤ 5000, on a n × n board subject to the following restrictions
• The i-th rook can only be placed within the rectangle given by its left-upper corner (xli , yli) and its rightlower corner (xri , yri), where 1 ≤ i ≤ n, 1 ≤ xli ≤ xri ≤ n, 1 ≤ yli ≤ yri ≤ n.
• No two rooks can attack each other, that is no two rooks can occupy the same column or the same row.

Mean

8皇后+贪心的变形,变成5000皇后了~

你的任务是在N*N的棋盘上放N辆车,使得任意两辆车不互相攻击,且第i辆车在一个给定的矩形Ri内。

Analysis

需要把问题分解为在X轴和在Y轴上,当两部分都确定后,最终的位置也就唯一确定。

确定每个车在X轴上的位置:每辆车有一个可行区间,那么对这些点排序后取当前最优值就可以了,变成一个区间贪心问题。

Code

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int st, ed, id;
    bool operator < (const Node & rhs) const {
        return ed > rhs.ed;
    }
};
const int maxn = 5120;
int n, resx[maxn], resy[maxn];
Node vx[maxn], vy[maxn];

bool solve(Node *v, int *res) {
    sort(v + 1, v + n + 1, [](const Node &a, const Node &b) { return a.st < b.st; });
    priority_queue<Node> qu;
    for(int i = 1, cnt = 1; i <= n; ++i) {
        while(cnt <= n && v[cnt].st <= i)
            qu.push(v[cnt++]);
        if(qu.empty() || qu.top().ed < i)
            return false;
        Node node = qu.top(); qu.pop();
        res[node.id] = i;
    }
    return true;
}

int main() {
    while(~scanf("%d", &n), n) {
        for(int i = 1; i <= n; ++i) {
            scanf("%d%d", &vx[i].st, &vy[i].st);
            scanf("%d%d", &vx[i].ed, &vy[i].ed);
            vx[i].id = vy[i].id = i;
        }
        if(solve(vx, resx) && solve(vy, resy)) {
            for(int i = 1; i <= n; ++i)
                printf("%d %d\n", resx[i], resy[i]);
        } else {
            printf("IMPOSSIBLE\n");
        }
    }
    return 0;
}

欢迎留言