Hdu 4864(Task 贪心)
题意：给定n台机器和m个任务，任务和机器都有工作时间值和工作等级值，一个机器只能执行一个任务，且执行任务的条件位机器的两个值都大于等于任务的值，每完成一个任务可获奖励500x+2y。求完成最多任务前提下可获得最高奖励，输出任务数和奖励数。
解法：对机器和任务进行排序，x和y都从大到小排。循环考察每一个任务，把满足每一个任务x值的机器等级都记录下来，然后用满足任务等级的最小等级机器完成此任务。这样的做法可以保证：
- 前面的任务执行比后面的任务可获的奖励更高（排序）
- 满足前面任务x值的机器一定满足后面的任务
- 完成任务数是最多的(每次使用最小化等级)
import java.io.*;
import java.util.*;
public class Main
{
private static final int N=100005;
private static class node{
int x,y;
};
private static class cmp implements Comparator<node>{
@Override
public int compare(node a,node b){
if(a.x == b.x){
if(a.y==b.y) return 0;
return a.y<b.y?1:-1;
}
if(a.x==b.x) return 0;
return a.x<b.x?1:-1;
}
}
public static int book[]=new int[105];
public static node s1[]=new node[N];
public static node s2[]=new node[N];
public static void main(String[] args){
for(int i=0;i<N;i++){
s1[i]=new node();
s2[i]=new node();
}
int n,m,i,j,cnt;
long sum;
Scanner sc=new Scanner(new InputStreamReader(System.in));
while(sc.hasNext()){
n=sc.nextInt();
m=sc.nextInt();
for(i = 0; i<n; i++){
s1[i].x=sc.nextInt();
s1[i].y=sc.nextInt();
}
for(i = 0; i<m; i++){
s2[i].x=sc.nextInt();
s2[i].y=sc.nextInt();
}
Arrays.sort(s1,0,n,new cmp());
Arrays.sort(s2,0,m,new cmp());
sum=cnt=0;
Arrays.fill(book,0);
for(i=0,j=0;i<m;i++){
while(j<n&&s1[j].x>=s2[i].x){
book[s1[j].y]++;
j++;
}
for(int k=s2[i].y;k<=100;k++){
if(book[k]>0){
book[k]--;
sum+=(s2[i].x*500+s2[i].y*2);
cnt++;
break;
}
}
}
System.out.println(cnt+" "+sum);
}
sc.close();
}
}