題意：你的任務(wù)是在n*n的棋盤上放 n 小于5000 個車 使得任意兩個車不互相攻擊 且第i個車在一個給定的矩形ri之內(nèi) ?給出該矩形左上角坐標(biāo)和右下角坐標(biāo)四個點 ?必須滿足放車的位置在矩形內(nèi) ?邊上也行 ?如果無解輸出IMPSSIBLE

行與列是獨立的 ? 所以可以分割成兩個一模一樣的子問題 ? 貪心

要以右邊界升序排序 ? 我一開始按照左邊界排序錯了 ? 舉個例子 ? 1-1 ?1-3 2-2 ?這樣的話就會錯 ? ? 1-1 2-2 1-3才對 ?

還有就是注意細(xì)節(jié) ?sort 從一開始的話 都要加一，，，

#include<bits/stdc++.h> using namespace std; #define N 5010 int n,k; int vis[N]; struct node {int id;int x,y;int x1,x2,y1,y2;}chess[N];bool cmp1(node a,node b){return a.x2<b.x2||(a.x2==b.x2&&a.x1<b.x1);} bool cmp2(node a,node b){return a.y2<b.y2||(a.y2==b.y2&&a.y1<b.y1);} bool cmp3(node a,node b){return a.id<b.id;} int main() {while(cin>>n,n){int flag=1;for(int i=0;i<n;i++){chess[i].id=i;scanf("%d%d%d%d",&chess[i].x1,&chess[i].y1,&chess[i].x2,&chess[i].y2);}sort(chess,chess+n,cmp1);memset(vis,0,sizeof vis);for(int i=0;i<n;i++){int ok=0;for(int j=chess[i].x1;j<=chess[i].x2;j++){if(!vis[j]){ok=1;vis[j]=1;chess[i].x=j;break; }//把chess里面的i寫成了j 強行將自己dubug了半個小時。。。 }if(!ok){flag=0;}}sort(chess,chess+n,cmp2);memset(vis,0,sizeof vis);for(int i=0;i<n;i++){int ok=0;for(int j=chess[i].y1;j<=chess[i].y2;j++){if(!vis[j]){ok=1;vis[j]=1;chess[i].y=j;break; }}if(!ok){flag=0;}}sort(chess,chess+n,cmp3);if(flag)for(int i=0;i<n;i++)printf("%d %d\n",chess[i].x,chess[i].y);else printf("IMPOSSIBLE\n");} }

?

LRJ的代碼 ?更慢

#include<cstdio> #include<cstring> #include <algorithm> using namespace std;// solve 1-D problem: find c so that a[i] <= c[i] <= b[i] (0 <= i < n) bool solve(int *a, int *b, int *c, int n) {fill(c, c+n, -1);for(int col = 1; col <= n; col++) {// find a rook with smalleset b that is not yet assignedint 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], y1[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], &y1[i], &x2[i], &y2[i]);if(solve(x1, x2, x, n) && solve(y1, y2, y, n))for (int i = 0; i < n; i++) printf("%d %d\n", x[i], y[i]);elseprintf("IMPOSSIBLE\n");}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/bxd123/p/10432674.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的8-4 Fabled Rooks uva11134的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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