第一想法是用递归 try1：没有深刻理解题意，写成了二重循环，也就是nn次，但其实行和列没关系，只要n2即可 try2：第一次写re了，后来工工整整地写，终于是tle了，思想不对，n=5000，用递归确实会爆， 第二次 贪心 try1：看别人的博客后，知道这原来是一道贪心题，而贪心的思想是每一次贪心都更接近目标，而不是没有依据地瞎推公式，也从别人的博客里才明白这道题目的考点，x和y是独立的，2种是一样的求法，可以看做一个坐标轴上，给了n个区间，现在要在这每个区间上都取一个点，这每个点都得不一样，也就是说1-n的每一点都要取到，并且分布在不同的区间上。 我的贪心法是，用结构体保留各个区间，放入优先队列all，all的优先序列是左区间越小越在前面否则就是右坐标越在前面越在前面，第一步，先取出右边界相同的区间，都放入temp，保存下一个未取出的区间的右坐标a，第二步，从temp中取出左区间大于a的坐标，temp的优先序列是左边界越大的越在前面，否则就右坐标越大的越在前面，并从最右边开始对给取出的区间定点。如果有某个点没有区间可以取，那么就失败了。 贪心的原理来源于，对于一段区间，若只有一个区间在这里有范围，那么贪心的思想就是在这里必须取，同理，对于一段区间，只有这k个区间在这里有范围且右边界相同，那么贪心的思想就是在这里取左边界最大的（范围最短的）。而对于一个不能取的范围，可以从各个边界中删除这一段，实现剩余各个区间的右边界相同，如【1,9】，而【7,9】已经不能取了，那么就把【1,9】看作【1,7】。
先记下想法，代码还在wa，还没实现~~
好久没有这样写一道题，终于在晚上12点20ac了！ 改的过程 1.要清楚这题想的贪心原理，是一个独一无二的空白区域，那么是 if(th<=now.b)break;，而不是用当前的左坐标与前一个的用未取出的右坐标去比。 2.结构体定义排序 对于all，排序的优先序列应该是当右坐标不想等时，右坐标越大越在前面，否则左坐标越大越在越在前面，在这个地方错了， 所以样例 3 1 1 3 3 1 1 3 3 2 2 2 2 这个过不去。 对于temp，就是定义了greater,的，它的排序要注意了。 排序后，最好测试一下。
3.优先队列中如果没有元素了，它的顶元素会是那个旧元素，所以有一个地方，一直在循环，导致错误。
#include<cstdio> #include<queue> #include<stdlib.h> using namespace std; struct re { int a,b,num; bool operator<(const re &c)const{return b!=c.b? b<c.b:a<c.a;} bool operator>(const re &c)const{return a!=c.a? a<c.a:b<c.b;} }; int n; const int maxn=5e3+10; priority_queue<re>quex,quey; priority_queue<re,vector<re>,greater<re> >temp; int cnt=0; bool solve(int *ans,priority_queue<re>que) { int th=n; re get,now; while(1) { if(!que.empty()){get=que.top();que.pop();temp.push(get);} while(!que.empty()) { now=que.top(); if(now.b!=get.b)break; que.pop(); temp.push(now); } if(que.size()==0)now.b=0; while(1) { get=temp.top(); if(th<=now.b)break; if(get.a<=th&&get.b>=th) { ans[get.num]=th--; temp.pop(); if(th==0)return 1; if(temp.size()==0)break; } else return 0; } } } int main(void) { while(scanf("%d",&n)&&n) { re tem1,tem2; while(!temp.empty())temp.pop(); while(!quex.empty())quex.pop(); while(!quey.empty())quey.pop(); for(int i=1;i<=n;i++) { scanf("%d %d %d %d",&tem1.a,&tem2.a,&tem1.b,&tem2.b); tem1.num=i; tem2.num=i; quex.push(tem1); quey.push(tem2); } int anx[maxn],any[maxn]; if(solve(anx,quex)==0){printf("IMPOSSIBLE\n");continue;} if(solve(any,quey)==0){printf("IMPOSSIBLE\n");continue;} for(int i=1;i<=n;i++)printf("%d %d\n",anx[i],any[i]); } return 0; }