UVA 11134 传说中的车 Fabled Rooks 题解

按照常规思路，一定是分解成两个一维问题：使 $1 \sim n$ 中每个数都在唯一的区间 $[l,r]$ 中（每个区间只能包含一个数）。如果一个车的横坐标能像上面一样做，纵坐标也能像上面那样做，那么这个车一定是符合题目要求的。

之后的贪心策略不好想。也许你会想要按照 $r$ 从大到小排序，再用一个 $O(n)$ 的倒序扫描完成问题：

bool cmp (Seg a, Seg b) {
    if (a.r == b.r)
        return a.l < b.l;
    return a.r > b.r;
}
std::sort(a + 1, a + 1 + n, cmp);
int i = n, j = 1;
while (i >= 1 && j <= n) {
    if (a[j].l <= i && i <= a[j].r)
         rook[a[j].id] = i--;
     ++j;
}
if (i >= 1)
     return false;
else
    return true;

但对下面两个数据，无论 $l$ 怎么排都会输出错误结果，因为这不能保证一遍扫描时就能确定每个坐标：

#1:
[1,3],[1,3],[2,2]
#2:
[1,1],[3,4],[1,3],[2,3]

既然这样不行，那可以再尝试按照 $r$ 从小到大排序， $r$ 相同时 $l$ 从小到大排序，坐标从小到大扫描。这样对于每个坐标都可以选取占据空间尽量小的位置，让后面尽量都能选。这个也会遇到和上面同样的问题，所以需要用 $O(n^2)$ 算法，对于每个坐标都找所有的区间，第一个找到的区间就能包含它。用上面的方法，当横纵坐标都能找到时就说明有一组解。

struct Seg {
    int l, r, id;//id表示这个区间是第几个输入的
};
bool cmp(Seg a, Seg b) {
    if (a.r == b.r)
        return a.l < b.l;
    return a.r < b.r;
}
int n;
bool vis[5003];
bool work(Seg a[], int rook[]) {//rook[id]表示区间id包含的坐标
    std::sort(a + 1, a + 1 + n, cmp);
    memset(vis, 0, sizeof vis);//用vis[id]表示区间id是否已用过
    int i = 1;
    while (i <= n) {
        bool found = 0;//found表示是否找到
        for (int j = 1; j <= n; j++)
            if (a[j].l <= i && i <= a[j].r && !vis[a[j].id]) {
                found = 1;
                rook[a[j].id] = i++, vis[a[j].id] = 1;
                break;
            }
        if (!found)
            return 0;
    }
    return 1;
}

完整代码不贴了。