首页 > 代码库 > HDU 4864 Task

HDU 4864 Task

2024-07-13 11:47:47   216人阅读

题意：

　　N台机器，M个任务，机器和任务分别有一个time值，和level值。每台机器上最多只能运行一个任务，而且机器的time值和level值要分别大于等于该任务的值。完成一个任务会获得(500*time+2*level)的价值。

　　求能完成的最多任务数，和这种情况下可以获得的最大价值。

思路：

　　因为数据范围，不能用网络流做。然后发现时间的收益远远大于level的收益，所以在选取任务的时候只需要优先考虑time。所以，在能选到的情况下，应该尽可能选time最大的，然后在time相同时，选level最大的。

　　所以想到了贪心，把机器按level分组，然后降序排列，对于一个任务，如果当先level中可用的最大time都不能选择该任务，那么比他小的一定也不能选择。然后把任务，按照能获得的价值，降序排列。所以，现在选择的一定是现在状态下收益最大的。然后，枚举就行了。

代码：

　　

#include <cstdio>#include <cstring>#include <algorithm>#include <functional>using namespace std;typedef __int64 ll;const int MAXN = 100005;const int LEVEL = 101;struct task {    int lv;    int time;    bool operator < (const task &x) const {    if (time!=x.time)            return time > x.time;    return lv > x.lv;    }}ts[MAXN];int ma[LEVEL][MAXN];int cnt[LEVEL];int use[LEVEL];int n, m;bool cmp(const int &x, const int &y) {    return x > y;}void input() {    memset(cnt, 0, sizeof(cnt));    int t, lv;    for (int i = 0; i < n; i++) {        scanf("%d%d", &t, &lv);        ma[lv][cnt[lv]++] = t;    }    for (int i = 0; i < m; i++) {        scanf("%d%d", &ts[i].time, &ts[i].lv);    }}void solve() {    for (int i = 0; i < LEVEL; i++)        sort(ma[i], ma[i]+cnt[i], cmp);    sort(ts, ts+m);    int num = 0;    ll cost = 0;    memset(use, 0, sizeof(use));    for (int i = 0; i < m; i++) {        for (int j = ts[i].lv; j < LEVEL; j++) {            if (use[j]<cnt[j] && ts[i].time<=ma[j][use[j]]) {                num++;                cost += ts[i].time*500 + ts[i].lv*2;                use[j]++;                break;            }        }    }    printf("%d %I64d\n", num, cost);}int main() {    #ifdef Phantom01        freopen("1004.txt", "r", stdin);    #endif // Phantom01    while (scanf("%d%d", &n, &m)!=EOF) {        input();        solve();    }    return 0;}
HDU 4864


联系
我们