首页 > 代码库 > hdu 4864 task 贪心

hdu 4864 task 贪心

2024-07-13 15:33:27   224人阅读

 

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 qi43             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\n",ans1,ans2);61     }62     return 0;63 }


联系
我们