hdu4864
题意：
有n个机器，m个任务，n,m<=100000，每个机器都有工作时间的最大限制xi(0<xi<1440)和完成的最大难度yi(0<=yi<=100)，每个任务也有所需要的时间和难度，只要机器的时间大于等于任务，难度大于等于任务，该任务就可以被机器完成，每完成一个任务就可以得到500*xi+2*yi的money，问最多能有多少个任务被完成，并且保证完成任务数量最多的情况下，所得到的money最多是多少？
思路：
由于money是500*x+2*y，而y最大是100，则只要保证任务的x最大，那么得到的钱一定是最多的。
将任务按照时间x从大到小排序，然后依次用任务查找机器，时间x从大到小保证了得到的钱是最多的，然后每个任务找出大于该任务难度y且与难度y最接近的机器完成该任务。现在有个问题需要证明一下，每次找难度最接近的机器，那么时间x只是大于任务x即可，时间是否物尽其用了呢？是否有浪费呢？不会，因为任务的x是从大到小排序遍历，如果任务找到了一个大于自身时间x的机器，就用，即使有别的x更大的机器没有被用，但是可以留下来给别的任务用。
比赛的时候代码WA，虽然也是贪心，但是用的机器查找任务，导致x做到了物尽其用，y并没有做到，so WA~
不要迷迷糊糊的写，要严谨的证明全对再下手写~
/*===============================================================
* Copyright (C) 2014 All rights reserved.
*
* File Name: hdu4864.cpp
* Author:sunshine
* Created Time: 2014年07月23日
*
================================================================*/
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm> using namespace std; #define N 100005 struct node{
int x,y;
bool operator < (const node &n1) const{
if(x != n1.x) return x > n1.x;
return y > n1.y;
}
}task[N]; int main(){
int n,m;
int x,y;
while(cin >> n >> m){ multiset<int> S[];
long long res = ;
int cnt = ; for(int i = ;i < n;i ++){
scanf("%d%d", &x, &y);
S[y].insert(x);
} for(int i = ;i < m;i ++){
scanf("%d%d", &task[i].x, &task[i].y);
} sort(task,task+m); for(int i = ;i < m ;i ++){
x = task[i].x;
y = task[i].y; for(int j = y;j <= ;j ++){
if(S[j].empty()) {
continue;
} multiset<int>::iterator it = S[j].lower_bound(x); if(it == S[j].end() || *it < x){
continue;
}else{
cnt ++;
res += * x + * y;
S[j].erase(it);
break;
}
}
}
printf("%d %I64d\n",cnt,res);
}
return ;
}
hdu4268
题意：
Alice有n个纸片，Bob有n个纸片，n<=100000每个纸片有长度和宽度，已知这2*n个纸片的长和宽，求Alice最多能覆盖Bob多少张纸片，每张纸片只能被用一次。
思路：
将这2*n张纸片按照长x从大到小排序，y从大到小排序，如果x、y相等，则Alice的纸片排在前面，用Bob去查找Alice，即Alice所有的纸片插入到set中，但是并不是一下子全部插入到set中，而是边插入set处理边求解Bob的第i张纸片能否被覆盖，这样能够保证之前插入的所有纸片的长x都大于等于自身的x，每次遇到Alice的纸片则插入到set中，每次遇到Bob的纸片则在set中查找刚好大于等于y的第一个Alice的纸片，然后把它删除，依次。
/*===============================================================
* Copyright (C) 2014 All rights reserved.
*
* File Name: hdu4268.cpp
* Author:sunshine
* Created Time: 2014年07月23日
*
================================================================*/
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm> using namespace std; #define N 100010 struct node{
int x,y;
bool id;
}p[*N]; int cmp(node n1,node n2){
if(n1.x == n2.x && n2.y == n2.y) return n1.id > n2.id;
if(n1.x != n2.x) return n1.x > n2.x;
return n1.y > n2.y;
} int main(){
int cas;
int n;
int x,y;
scanf("%d", &cas);
while(cas --){
scanf("%d", &n);
for(int i = ;i < n;i ++){
scanf("%d%d", &p[i].x, &p[i].y);
p[i].id = ;
} for(int i = n;i < * n;i ++){
scanf("%d%d", &p[i].x, &p[i].y);
p[i].id = ;
} sort(p,p + * n,cmp);
multiset<int>S;
int cnt = ;
for(int i = ;i < * n;i ++){
if(p[i].id){
S.insert(p[i].y);
}else{
y = p[i].y;
multiset<int>::iterator it = S.lower_bound(y); if(it == S.end() || *it < y){
continue;
}else{
S.erase(it);
cnt ++;
}
}
}
printf("%d\n",cnt);
}
return ;
}