首页 > 代码库 > HDU 4864Task(多校联合训练1)(贪心)
HDU 4864Task(多校联合训练1)(贪心)
题目地址:HDU4864
这题又是一上来认为是最小费用流,但是边太多,果然,敲完交上去后不断TLE。。小优化了两次也没过。。。sad。。
后来看了题解才发现是贪心。。。贪心也不好想。大体思路是很好想的,就是先都按时间从大到小排序,再遍历任务,从机器里找能匹配的,并在能匹配的里边找等级尽量小的与之匹配。对我来说的突破点在于找能匹配的机器时不是每次都要重新找一遍,而是可以直接利用以前找到的。这就避免了n^2的复杂度。这样的时间复杂度就只有m*100,明显不会超时。
代码如下:
#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include<algorithm> using namespace std; int _hash[110]; struct node { int time, lv; } task[110000], mac[110000]; int cmp(node x, node y) { if(x.time==y.time) return x.lv>y.lv; return x.time > y.time; } int main() { int n, m, i, j, num; __int64 ans; while(scanf("%d%d",&n,&m)!=EOF) { num=0; ans=0; for(i=0; i<n; i++) { scanf("%d%d",&mac[i].time,&mac[i].lv); } for(i=0; i<m; i++) { scanf("%d%d",&task[i].time,&task[i].lv); } sort(mac,mac+n,cmp); sort(task,task+m,cmp); j=0; memset(_hash,0,sizeof(_hash)); for(i=0; i<m; i++) { while(j<n&&mac[j].time>=task[i].time) { _hash[mac[j].lv]++; j++; } for(int k=task[i].lv; k<=100; k++) { if(_hash[k]) { _hash[k]--; num++; ans+=500*task[i].time+2*task[i].lv; break; } } } printf("%d %I64d\n",num,ans); } return 0; }
HDU 4864Task(多校联合训练1)(贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。