自己一开始想的是如果中间的任意一颗棋子[1,n] 该怎么选择位置，根据多个区间的话，这也想下去的确好像有办法，把各个区间想重叠的地方 记录下来，则如果某个地方只有1次覆盖，则那个地方的数字只能由那个区间提供。 但是这样也比较麻烦，参考了别人的代码后才发现 如果你仅仅从最左边开始，这样就只需要考虑其右边一边了（如果你一开始就想放中间的话，要考虑左右两边的问题），这样的话再只考虑一边的情况下，肯定是选择当前区间更小的棋子，比如两个区间1，3和1，5。我们想在位置1放一颗棋子的时候肯定选择第一个区间，应该第二区间大了（要想清楚为什么大了不好），这样选好位置1的棋子后，又开始从位置2开始，这是因为位置1已经选好了，位置2从而也就只考虑右边一边的情况了。
#include<iostream> #include<algorithm> #include<cassert> #include<string> #include<sstream> #include<set> #include<bitset> #include<vector> #include<stack> #include<map> #include<queue> #include<deque> #include<cstdlib> #include<cstdio> #include<cstring> //#include<cmath> #include<ctime> #include<cctype> #include<functional> using namespace std; #define me(s) memset(s,0,sizeof(s)) #define rep(i,n) for(int i=0;i<(n);i++) typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; typedef pair <int, int> P; bool solve(int*a,int*b,int*c,int n)//解决一维的问题：找一个c，使得a[i]<=c[i]<=b[i] { fill(c,c+n,-1); for(int col=1;col<=n;col++) { int rook=-1,minb=n+1; for(int i=0;i<n;i++) if(c[i]<0&&b[i]<minb&&col>=a[i])//找一个没有安排过的车，它的b[i]最小 { rook=i;minb=b[i]; } if(rook<0||col>minb)return false; //如果没有找到，或者虽然找到了，但是最大范围小于col,则无解 c[rook]=col; } return true; } const int N=5000+5; int n,x1[N],y1[N],x2[N],y2[N],x[N],y[N]; int main() { while(~scanf("%d",&n)&&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]); else puts("IMPOSSIBLE"); } }