題意：
? ? ? 給你一個(gè)n*n的棋盤，讓你在棋盤上放n個(gè)棋子，要求是所有棋子不能相互攻擊（同行或者同列就會(huì)攻擊），并且每個(gè)棋子都有一個(gè)限制，那就是必須在給定的矩形r[i]里，輸出每個(gè)棋子的位置，special Jude。


思路：
? ? ? 看完后第一反應(yīng)就是匈牙利（哎！慚愧啊。）結(jié)果想著怎么建圖，想了一會(huì)呵呵了，果斷想別的方法，其實(shí)這個(gè)題目設(shè)計(jì)到一個(gè)小思想非常好，那就是把整體分解，這個(gè)題目說的是什么？是每個(gè)棋子都限制了一個(gè)矩形范圍，矩形范圍又是什么？是不是就是xl<=x<=xr&&rl<=y<=yr,其實(shí)x和y我們可以分開考慮，可以分開的原因就是x和y之間沒有限制因素，也不會(huì)相互影響，就像是中學(xué)時(shí)學(xué)的速度分解一樣，這個(gè)就是這個(gè)題目的關(guān)鍵點(diǎn)，想到這個(gè)AC的可能性就很大了，分解后我們要處理的就是給你一些區(qū)間限制，然后在每個(gè)區(qū)間內(nèi)都必須選擇一個(gè)點(diǎn)放東西，最后要求同一個(gè)點(diǎn)不能放兩個(gè)東西，也就是本題目的同一行或者一列不能放兩個(gè)其子一樣，然后就是貪心了，怎么貪心呢？我們可以把每個(gè)區(qū)間都按照右端點(diǎn)從小到大排序，然后我們從前往后貪心，右端點(diǎn)越小的“自由性”越小，所以要先處理，所以放在前面，對于每一斷，我們就從這個(gè)段的做端點(diǎn)開始找，找第一個(gè)沒被占用的點(diǎn)，占用上就行了，如果都找到右端點(diǎn)了還沒找到可以用的點(diǎn)，那么就直接沒解了，x和y都是這么處理的，找的時(shí)候我用的是set容器總的時(shí)間復(fù)雜度是O(n*log(n))，如果不想用set直接暴力找也應(yīng)該不會(huì)超時(shí)，時(shí)間復(fù)雜度是O（n*n）.




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


#define N 5000 + 10


using namespace std;


typedef struct
{
? ?int l ,r ,id;
}EDGE;


int AnsX[N] ,AnsY[N];
EDGE X[N] ,Y[N];
set<int>set1 ,set2;


bool camp(EDGE a ,EDGE b)
{
? ?return a.r < b.r;
}


int main ()
{
? ?int i ,n;
? ?int x1 ,x2 ,y1 ,y2;
? ?while(~scanf("%d" ,&n) && n)
? ?{
? ? ? set1.clear() ,set2.clear();
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? {
? ? ? ? ?scanf("%d %d %d %d" ,&x1 ,&y1 ,&x2 ,&y2);
? ? ? ? ?X[i].l = x1 ,X[i].r = x2;
? ? ? ? ?Y[i].l = y1 ,Y[i].r = y2;
? ? ? ? ?X[i].id = Y[i].id = i;
? ? ? ? ?set1.insert(i);
? ? ? ? ?set2.insert(i);
? ? ? }
? ? ? set1.insert(10000000);
? ? ? set2.insert(10000000);
? ? ? sort(X + 1 ,X + n + 1 ,camp);
? ? ? sort(Y + 1 ,Y + n + 1 ,camp);
? ? ? int mk = 0;
? ? ? for(i = 1 ;i <= n && !mk ;i ++)
? ? ? {
? ? ? ? ?int tmpx = *set1.lower_bound(X[i].l);
? ? ? ? ?if(tmpx > X[i].r) mk = 1;
? ? ? ? ?AnsX[X[i].id] = tmpx;
? ? ? ? ?set1.erase(tmpx);
? ? ? ? ?
? ? ? ? ?int tmpy = *set2.lower_bound(Y[i].l);
? ? ? ? ?if(tmpy > Y[i].r) mk = 1;
? ? ? ? ?AnsY[Y[i].id] = tmpy;
? ? ? ? ?set2.erase(tmpy);
? ? ? }
? ? ??
? ? ? if(mk)
? ? ? {
? ? ? ? ?puts("IMPOSSIBLE");
? ? ? ? ?continue;
? ? ? }
? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? printf("%d %d\n" ,AnsX[i] ,AnsY[i]);
? ?}
? ?return 0;
}
? ?
? ? ??
? ? ??

總結(jié)

以上是生活随笔為你收集整理的UVA11134传说中的车（放棋子）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。