题目描述
今天某公司有 $M$ 个任务需要完成。
每个任务都有相应的难度级别和完成任务所需时间。
第 $i$ 个任务的难度级别为 $y\_i$,完成任务所需时间为 $x\_i$ 分钟。
如果公司完成此任务,他们将获得($500 \\times x\_i + 2 \\times y\_i$)美元收入。
该公司有 $N$ 台机器,每台机器都有最长工作时间和级别。
如果任务所需时间超过机器的最长工作时间,则机器无法完成此任务。
如果任务难度级别超过机器的级别,则机器无法完成次任务。
每台机器一天内只能完成一项任务。
每个任务只能由一台机器完成。
请为他们设计一个任务分配方案,使得该公司能够最大化他们今天可以完成的任务数量。
如果有多种解决方案,他们希望选取赚取利润最高的那种。
输入格式
输入包含几个测试用例。
对于每个测试用例,第一行包含两个整数 $N$ 和 $M$,分别代表机器数量和任务数量。
接下来 $N$ 行,每行包含两个整数 $x\_i,y\_i$,分别代表机器最长工作时间和机器级别。
再接下来 $M$ 行,每行包含两个整数 $x\_i,y\_i$,分别代表完成任务所需时间和任务难度级别。
输出格式
对于每个测试用例,输出两个整数,代表公司今天可以完成的最大任务数以及他们将获得的收入。
数据范围
$1 \\le N,M \\le 100000$,
$0 < x\_i < 1440$,
$0 \\le y\_i \\le 100$
输入样例:
1 2
100 3
100 2
100 1
输出样例:
1 50004
算法
(暴力枚举) $O(n^2)$
write here…
时间复杂度
write here…
空间复杂度
write here…
C++ 代码
// 对每个点 [x,y] 我们优先匹配 500 * x + y * 2 更大的点.
// 由于 1 <= x <= 1440 且 0 < y <= 100 ,所以先匹配的点 x 值一定更大,后面考虑匹配的点的 x 值小于等于当前点的 x 值,
// 所以能和当前点匹配的点的 x 值一定满足后面匹配点的 x 值的要求,所以我们为了使剩下的点能尽可能的匹配上,
// 我们当前点应当在 x 值满足条件下,尽可能选 y 值小的点进行匹配,x 值随便即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 100;
struct node
{
int x,y;
bool operator<(node B) const
{
return x * 500 + 2 * y < 500 * B.x + 2 * B.y;
}
}p[N];
int n,m;
multiset<int> mach[110]; // mach[i] 存储的是所有还没有用掉的 i 级机器。
int up[110]; // i 级机器 x 的最大值
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++)
{
int x,y;
cin >> x >> y;
mach[y].insert(x);
up[y] = max(up[y],x);
}
for(int i=1;i<=m;i++) cin >> p[i].x >> p[i].y;
sort(p+1,p+m+1);
int cnt = 0 , sum = 0;
for(int i=m;i>=1;i--)
{
for(int j=p[i].y;j<=100;j++)
{
if(up[j] < p[i].x) continue;
cnt ++ , sum += 500 * p[i].x + 2 * p[i].y;
mach[j].erase(prev(mach[j].end()));
if(mach[j].size()) up[j] = *prev(mach[j].end());
else up[j] = 0;
break;
}
}
cout << cnt << " " << sum << '\n';
}