续续 Codeforces 596 C Wilbur and Points

传送门：
http://codeforces.com/contest/596/problem/C

附上那份符合我当初屌丝想法的只排序不需要任何数据结构的写法
其实本质思想都是贪心，即先通过排序找到每个w[i]所对应的点号，然后保存下来
具体找法还是贪心去找，即x小优先，否则y小优先！！！！！
然后再Ｏ（ｎ）扫一遍去判断合法性就ｏｋ了，其实我这个方法也是蛮优美的，因为它只需要把两边都排次序就可以完成匹配了。。。
不过就是我刚开始想的方法就是错的（虽然大概思想是对的），我的排序方法被样例给带偏了，这题首要想法就应该是贪心！！！
一共对两个数组排两次序，第一次是为了记录位置，第二次是为了恢复原来的序列，然后进行判断，哎，这么裸的想法，我当时怎么就没想到要恢复原序列再Ｏ（ｎ）扫一遍判断合法性呢？？？

注意这种写法容易忽略掉的一点就是在对权值排序的时候如果相等的话要保证id的有序性，因为这道题目的本质就是判断给定的权值序列能否构成，如果不能保证之前的有序性就肯定会出问题的！！！！
（符合我前两份代码中确定解的时候的过程）
这份代码的优美之处就在于，它巧妙地利用第一次排序之后的结果把相应的位置记录了下来，记录下来了每一个w在原先线段序列中的位置！！！！
现在一看其实这题真的是蛮sb的！！！！
就是贪心加判断就ok了！！！！！

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define For(i,n) for(int i=1;i<=n;i++)
#define Dor(i,n) for(int i=n;i>=1;i--)
#define s(n) scanf("%d",&n)
#define p(n) printf("%d\n",n)
#define maxn 100000+10
#define ms(n) memset(n,0,sizeof(n))
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const double eps=1e-8;
const int inf=0x3f3f3f3f;
int n;
struct node{int x,y,w,id,pre;
}a[maxn],b[maxn];
bool cmp(node a, node b)  
{if(a.w!=b.w) return a.wif(a.x!=b.x) return a.xif(a.y!=b.y) return a.ybool cmp1(node a,node b)
{if(a.w==b.w) return a.idreturn a.wbool cmp2(node a,node b)
{return a.idint main()
{s(n);for(int i=0;ifor(int i=0;iint flag=1;for(int i=0;iif(a[i].w!=b[i].w){flag=0;break;}else b[i].pre=a[i].id;}if(!flag) {puts("NO");return 0;}sort(a,a+n,cmp2);sort(b,b+n,cmp2);flag=1;for(int i=1;iif((a[b[i].pre].x>a[b[i-1].pre].x||a[b[i].pre].y>a[b[i-1].pre].y)){continue;}else {flag=0;break;}}   if(flag){puts("YES");for(int i=0;iprintf("%d %d\n",a[b[i].pre].x,a[b[i].pre].y);}}else puts("NO");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！