题解：P10464 Task

iamajcer · 2024-08-20 20:35:33 · 题解

思路

首先，要求收益最大化，且选择方式没后效性，可以很自然的想到贪心。

注意到题目中给定 x<1440，y\le100，且贡献为 (500\times x_i+2\times y_i)，y 取到最大值也没有 x 的贡献大。我们可以对于每个机器，任务进行排序。按照 x 为第一关键字，y 为第二关键字排序。

排完序之后，确保了 x_i 是单调递减的，这一点很重要，在后续我会反复强调。我们现在就可以枚举每一个任务，看看是否能完成。对于每一个任务，假设先不考虑等级限制，如果时间长的任务我们可以完成，那么时间短的任务更加不用说了，肯定可以完成。这样我们考虑用贪心的思想，用等级最低且能完成这个任务的机器才是最优的，这样可以节省更多高等级机器留着以后去用，因为 x_i 是单调递减的，所以对于 x_i 不用担心，前面的机器能完成，后面的机器更加能完成，主要就是 y_i 的限制了。

所以我们可以维护一个 multiset，存储所有能够完成该任务的机器的等级，注意，由于 x_i 的单调性，我们不用每一次重新维护 multiset，而是继承上一次的值。

基于贪心，且 multiset 自带排序功能，我们可以二分查找第一个大于等于任务等级的机器等级，然后累加答案。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=100005;

struct node
{
    int x, y;
}a[N], b[N];
int n, m, cnt=0;
long long ans=0;
multiset<int> s;
multiset<int>::iterator it;
bool cmp(node a, node b)
{
    if (a.x==b.x) return a.y>b.y;
    return a.x>b.x;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++) scanf("%d%d", &a[i].x, &a[i].y);
    for (int i=1; i<=m; i++) scanf("%d%d", &b[i].x, &b[i].y);

    sort(a+1, a+1+n, cmp);
    sort(b+1, b+1+m, cmp);

    int h=1;
    for (int i=1; i<=m; i++)
    {
        for (int j=h; j<=n; j++)
        {
            if (a[j].x>=b[i].x)
            {
                s.insert(a[j].y);
                h=j+1; //因为此时满足条件，下一次循环从本次循环到的数往后一个数开始循环
            }
            else
            {
                h=j; //因为此时不满足条件，下一次就从本次循环到的数开始循环
                break;
            }
        }

        it=s.lower_bound(b[i].y);
        if ((it)!=(s.end()))
        {
            ans+=500*b[i].x+2*b[i].y;
            cnt++;
            s.erase(it);
        }
    }

    printf("%d %lld", cnt, ans);
    return 0;
}