广州排名推广,win10系统优化,dnf怎么做提卡网站,深圳做网站的公司的区域题意#xff1a;你的任务是在n*n的棋盘上放 n 小于5000 个车 使得任意两个车不互相攻击 且第i个车在一个给定的矩形ri之内 给出该矩形左上角坐标和右下角坐标四个点 必须满足放车的位置在矩形内 边上也行 如果无解输出IMPSSIBLE 行与列是独立的 所以可以分割成两个一模一… 题意你的任务是在n*n的棋盘上放 n 小于5000 个车 使得任意两个车不互相攻击 且第i个车在一个给定的矩形ri之内 给出该矩形左上角坐标和右下角坐标四个点 必须满足放车的位置在矩形内 边上也行 如果无解输出IMPSSIBLE 行与列是独立的 所以可以分割成两个一模一样的子问题 贪心 要以右边界升序排序 我一开始按照左边界排序错了 举个例子 1-1 1-3 2-2 这样的话就会错 1-1 2-2 1-3才对 还有就是注意细节 sort 从一开始的话 都要加一 #includebits/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.x2b.x2||(a.x2b.x2a.x1b.x1);}
bool cmp2(node a,node b){return a.y2b.y2||(a.y2b.y2a.y1b.y1);}
bool cmp3(node a,node b){return a.idb.id;}
int main()
{while(cinn,n){int flag1;for(int i0;in;i){chess[i].idi;scanf(%d%d%d%d,chess[i].x1,chess[i].y1,chess[i].x2,chess[i].y2);}sort(chess,chessn,cmp1);memset(vis,0,sizeof vis);for(int i0;in;i){int ok0;for(int jchess[i].x1;jchess[i].x2;j){if(!vis[j]){ok1;vis[j]1;chess[i].xj;break; }//把chess里面的i写成了j 强行将自己dubug了半个小时。。。}if(!ok){flag0;}}sort(chess,chessn,cmp2);memset(vis,0,sizeof vis);for(int i0;in;i){int ok0;for(int jchess[i].y1;jchess[i].y2;j){if(!vis[j]){ok1;vis[j]1;chess[i].yj;break; }}if(!ok){flag0;}}sort(chess,chessn,cmp3);if(flag)for(int i0;in;i)printf(%d %d\n,chess[i].x,chess[i].y);else printf(IMPOSSIBLE\n);}
} LRJ的代码 更慢 #includecstdio
#includecstring
#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, cn, -1);for(int col 1; col n; col) {// find a rook with smalleset b that is not yet assignedint rook -1, minb n1;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;
} 转载于:https://www.cnblogs.com/bxd123/p/10432674.html
