首页 > 代码库 > HDU4864(Task)
HDU4864(Task)
题目地址:Task
题目大意:
n台机器,m个任务,每台机器和任务都有两个值,机器的两个值都大于任务的两个值,这台机器才能完成这个任务,每台机器只能完成一个任务,问最大收益。
解题思路:
因为尽量处理时间大的任务,所以机器和任务先按时间从大到小排序,尽量找与task相接近的时间和等级,先将机器时间大于task1的所有机器按照机器的等级存入一个数组,然后按照task1的等级找最接近的处理机器,因为必须先处理时间高的任务,因为它需要乘500,一定很大,之所以找task1的等级找最接近,这样以保证后面taskn等级大的任务不受影响完成,依次类推。
代码:
1 /* 2 题意:n台机器,m个任务,每台机器和任务都有两个值,机器的两个值都大于任务的两个值, 3 这台机器才能完成这个任务,每台机器只能完成一个任务,问最大收益 4 思路:因为尽量处理时间大的任务,所以机器和任务先按时间从大到小排序,尽量找与task相接近的时间和等级, 5 先将机器时间大于task1的所有机器按照机器的等级存入一个数组,然后按照task1的等级 6 找最接近的处理机器,因为必须先处理时间高的任务,因为它需要乘500,一定很大,之所以找task1的等级 7 找最接近,这样以保证后面taskn等级大的任务不受影响完成,依次类推。 8 */ 9 10 /*网上的代码:*/11 #include <stdio.h>12 #include <string.h>13 #include <algorithm>14 using namespace std;15 16 struct node17 {18 int x,y;19 } s1[100005],s2[100005];20 21 int cmp(node a,node b)22 {23 if(a.x == b.x)24 return a.y>b.y;25 return a.x>b.x;26 }27 28 int main()29 {30 int n,m,i,j,cnt;31 __int64 sum;32 while(~scanf("%d%d",&n,&m))33 {34 for(i = 0; i<n; i++)35 scanf("%d%d",&s1[i].x,&s1[i].y);36 for(i = 0; i<m; i++)37 scanf("%d%d",&s2[i].x,&s2[i].y);38 sort(s1,s1+n,cmp);39 sort(s2,s2+m,cmp);40 cnt = sum = 0;41 int c[105] = {0};42 for(i = 0,j = 0; i<m; i++)43 {44 while(j<n && s1[j].x>=s2[i].x)45 {46 c[s1[j].y]++;47 j++;48 }49 for(int k = s2[i].y; k<=100; k++)50 {51 if(c[k])52 {53 c[k]--;54 sum+=(s2[i].x*500+s2[i].y*2);55 cnt++;56 break;57 }58 }59 }60 printf("%d %I64d\n",cnt,sum);61 }62 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。