hdu 4864 task 贪心

http://acm.hdu.edu.cn/showproblem.php?pid=4864

【题意】有n个机器每个机器都有一个最长工作时间和等级，m个任务，每个任务有一个需要花费的时间和任务等级，每个任务完成了可以得打到500*time+2*rank 块钱，一个机器只能对应做一个时间和等级都

小于等于的它自己的任务，求可以得到的最多的钱。

【思路】因为等级最大为100，100*2<500,对钱数等级影响的主要是time，对机器和任务对时间由大到小排序，时间最大的任务开始，找到时间符合的等级最小的机器。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<queue>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 queue<int > q[102];
 9 struct node{int t,r;}machine[100002],task[100002];
10 int cmp(node a,node b)
11 {
12     if(a.t==b.t)
13         return  a.r>b.r;
14     return a.t>b.t;
15 }
16 
17 int main()
18 {
19     int n,m;
20     while(~scanf("%d%d",&n,&m))
21     {
22         int ans1=0;
23         __int64 ans2=0;
24         for(int i=0;i<n;i++)
25             scanf("%d%d",&machine[i].t,&machine[i].r);
26         for(int i=0;i<m;i++)
27             scanf("%d%d",&task[i].t,&task[i].r);
28         sort(machine,machine+n,cmp);
29         sort(task,task+m,cmp);
30         int i=0,j=0;//i任务   j 机器
31 
32         for(int i=0;i<100;i++)
33         while(!q[i].empty())
34           q[i].pop();
35 
36         for(int i=0;i<n;i++)//  同一级的机器入队
37             q[machine[i].r].push(i);
38 
39         for(int i=0;i<m;i++)
40         {
41             int time,rank1;
42             time=task[i].t; rank1=task[i].r;//zhao ji qi
43             while(1)
44             {
45                 while(q[rank1].size()==0&&rank1<100)
46                     rank1++;
47                 if(rank1>=100)
48                     break;
49                 int temp=q[rank1].front();
50                 if(machine[temp].t>=time)    // 队列的第一个是这个等级时间最大的机器，第一个时间符合的就直接匹配，因为下一个任务的时间肯定等于或者小于此任务。
51                 {
52                     ans1++;
53                     ans2+=task[i].t*500+task[i].r*2;
54                     q[rank1].pop();
55                     break;
56                 }
57                 else rank1++;
58             }
59         }
60         printf("%d %I64d
",ans1,ans2);
61     }
62     return 0;
63 }