G.OfZorcsandAxes----贪心+STL

转载地址：http://www.cnblogs.com/liuweimingcprogram/p/6044994.html?utm_source=itdadao&utm_medium=referral

大牛的博客，把set用到出神入化

以下来自大牛：

一开始还以为要用二分图去做，但是复杂度也太高了，O(n * m)的话直接爆炸。

考虑贪心，考虑第i个东西优先选一个能选的，而且这个东西的值尽量小。

就是如果要<3, 3>的话，我希望找到有序对，其中x和y都最接近3， 3

那么这里就涉及到同时排序两个数，就是这两个数的优先级一样，而且二分找的时候也要同时比较两个数了

一开始还想用set的，但是这样重载运算符的set我没用过，重载成 return a 不知道为何，希望有大牛指点一二。

那么可以这样去想，先对x排序，如果x相同再对y排序，全部相同就按照被选的那个优先，就是m那堆数字有先。

这样做有什么好处呢？可以维护一个set，每次如果是m那堆数字的话，就扔去set那里，如果不是，就从set里面找，找的时候只需要比较y就行了，因为x已经保证严格成立了。

最后说一下set那里，自己写一个比较函数的话，就要考虑重复的元素，因为重复的元素会被自动删除的，但是我本来结构体那里就有了个id这个值，id是保证不同的了，id是我用来记录答案的，但是它还是去重了。现在试了发现，如果想id不同，就当成不同的元素的话，就要在你的cmp那里把id加上去比较，

这里坑了我太久了，一直wa9、

给个数据吧

6
2 5
4 3
4 3
4 3
4 3
4 2
6
5 6
4 3
4 3
4 2
4 3
4 3

代码：

#include 
#include 
#include 
#include 
#include 
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include 
#include 
#include 
#include 
#include