UVa 11134 Fabled Rooks (分解 + 贪心)

注意到行列互不影响，所以将行列分开考虑

问题转化为：给定 \(n\) 条线段，填入 \(n\) 个格子，使得每个线段都被填入一个格子，且同一个格子只能填入一个线段

贪心，一个一个格子来看，所以将所有线段按左端点排序，该格子可以填入左端点在该格子左边的所有线段，为了保证最优，

再将这些线段按右端点排序，将格子依次填入线段即可

注意不合法的情况：

1. 取出线段后，线段的右端点在该格子之前，此时该线段无法填入格子，不合法
2. 没有剩余线段的左端点在该格子的左边，此时该格子无法填入线段，不合法

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

const int maxn = 5010;

int n;

struct Seg{
	int id;
	int l, r;
	
	bool operator < (const Seg &x) const{
		return r > x.r;
	}
}a[maxn], b[maxn];

bool cmp(Seg p, Seg q){
	return p.l < q.l;
}

int x[maxn], y[maxn];

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘){ if(ch == ‘-‘) f = -1; ch = getchar(); } while(ch >= ‘0‘ && ch <= ‘9‘){ s = s * 10 + ch - ‘0‘; ch = getchar(); } return s * f; }

int main(){
	while(scanf("%d", &n) == 1 && n){
		int xl, yl, xr, yr;
		for(int i = 1 ; i <= n ; ++i){
			scanf("%d%d%d%d", &xl, &yl, &xr, &yr);
			a[i].l = xl, a[i].r = xr, a[i].id = i;
			b[i].l = yl, b[i].r = yr, b[i].id = i;
		}
		
		sort(a + 1, a + 1 + n, cmp);
		sort(b + 1, b + 1 + n, cmp);
		
		priority_queue<Seg> q;
		while(!q.empty()) q.pop();
		
		int pos = 1;
		int flag = true;
		for(int i = 1 ; i <= n ; ++i){
			while(a[pos].l <= i && pos <= n) {
				q.push(a[pos++]);
			}
			
			if(q.empty()) flag = false;
			
			if(!q.empty()){
				Seg u = q.top(); q.pop();
				if(u.r < i) {
					flag = false;
					break;
				}
				x[u.id] = i;
			}
		}	

		if(!flag){
			printf("IMPOSSIBLE\n");
			continue;
		}
		
		while(!q.empty()) q.pop();
		
		pos = 1;
		flag = true;
		for(int i = 1 ; i <= n ; ++i){
			while(b[pos].l <= i && pos <= n) {
				q.push(b[pos++]);
			}
			
			if(q.empty()) flag = false;
			
			if(!q.empty()){
				Seg u = q.top(); q.pop();
				if(u.r < i) {
					flag = false;
					break;
				}
				y[u.id] = i;
			}
		}	
		
		if(!flag){
			printf("IMPOSSIBLE \n");
			continue;
		}
		for(int i = 1 ; i <= n ; ++i){
			printf("%d %d\n", x[i], y[i]);
		}
	}
	return 0;
}

UVa 11134 Fabled Rooks (分解 + 贪心)

原文：https://www.cnblogs.com/tuchen/p/14844665.html