首页 > 代码库 > hdu 4869 Task(贪心)
hdu 4869 Task(贪心)
题目链接:hdu 4869 Task
题目大意:有n台机器,m个任务,每个机器和任务都有有xi和yi,要求机器的xi,yi均大于等于任务的xi和yi才能执行任务。每台机器一天只能执行一个任务。要求完成的任务数尽量多,并且说金额尽量大。完成每个任务的金额为xi?500+yi?2
解题思路:贪心,mach[i][j]表示等级为i,时间为j的机器数量,task[i][j]表示等级为i,时间为j的机器数量。每次优先减少i,因为对应等级减少100,对应的金额代价也不会减少超过500(即时间减少1)。
每次mach[i][j]要加上mach[i][j+1],即上面没有被使用的机器,tmp记录当前j下,等级大于i的机器个数。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef __int64 ll;
const int maxt = 1440;
const int maxd = 100;
int N, M;
int mach[maxd+10][maxt+10], task[maxd+10][maxt+10];
void init () {
int a, b;
memset(mach, 0, sizeof(mach));
memset(task, 0, sizeof(task));
for (int i = 0; i < N; i++) {
scanf("%d%d", &a, &b);
mach[b][a]++;
}
/*
for (int i = maxd; i >= 0; i--)
for (int j = maxt; j >= 0; j--)
mach[i][j] = mach[i][j] + mach[i+1][j] + mach[i][j+1] - mach[i+1][j+1];
*/
for (int i = 0; i < M; i++) {
scanf("%d%d", &a, &b);
task[b][a]++;
}
}
void solve () {
ll ans = 0;
int cnt = 0;
for (int j = maxt; j >= 0; j--) {
int tmp = 0;
for (int i = maxd; i >= 0; i--) {
mach[i][j] += mach[i][j+1];
tmp += mach[i][j];
int k = min(tmp, task[i][j]);
ans += (ll)k * (2LL * i + 500LL * j);
tmp -= k;
cnt += k;
for (int x = i; x <= maxd; x++) {
int p = min(mach[x][j], k);
k -= p;
mach[x][j] -= p;
if (k == 0)
break;
}
}
}
printf("%d %I64d\n", cnt, ans);
}
int main () {
while (scanf("%d%d", &N, &M) == 2 && N + M) {
init();
solve();
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。