天津大学

编程入门行业动态更新时间:2024-10-09 04:19:38

天津大学

为了更好的阅读体检，可以查看我的算法学习网
在线评测链接:P1324

题目内容

小C有一批服务器，服务器以算力作为指标。现他需要给服务器分配任务，每个服务器只能承接一个任务，每个任务需要足够算力的服务器才能完成，即任务所需要的算力 x x x应当小于服务器的算力 y y y。现小 C C C需要为这些服务器分配任务,你需要完成程序，确认最多可以处理任务的数量。

输入描述

多组测试样例，第一行包含一个整数 T T T表示样例个数。

每组样例第一行包含两个整数 M N MN MN，分别表示服务器数量和任务数量，第二行包含 M M M个整数，表示服务器的算力，第三行包含 N N N个整数，表示任务所需算力。

输出描述

对于每一组输入，输出一个整数，表示最多可以处理任务的数量。

样例

输入

输出

2
2

提示

第一个样例中，第二个服务器(算力 5 5 5）处理任务 1 1 1(需要算力 4 4 4)，第三个服务器(算力 6 6 6)处理任务 2 2 2(需要算力 5 5 5）即可。

第二个样例中，第一个服务器处理任务 3 3 3，第二个服务器处理任务 2 2 2，最多可处理 2 2 2个任务。

T ≤ 10 T\leq 10 T≤10

N ≤ 100000 N\leq100000 N≤100000

思路：贪心

可以从两个角度来思考这个贪心问题。

角度一

从算力需求最小的任务开始。
对于一个算力需求小的任务，如果找不到一个服务器算力满足其算力需求，那么对于算力需求大于这个任务的其他任务，必然也不能被完成。

此外，每个任务应该找到大于其算力需求的服务器，但是这个服务器的算力也应该尽可能小。留着算力更大的服务器给算力需求更大的任务。

角度二

从服务器算力最大的任务开始。
对于一个服务器算力大的服务器，如果找不到一个任务满足算力需求小于服务器算力，则对应算力更小的服务器，必然也找不到算力需求小于其算力的任务。

此外，每个服务器应该找到算力需求小于其服务器算力的任务，但是这个任务的算力也应该尽可能大。留着算力需求更小的任务给服务器算力更小的服务器。

大家如果觉得需要巩固本算法，可见:贪心相关题目专练 , 跟着我们刷，可入门到精通！！

代码

// 角度一
#include<bits/stdc++.h>
using namespace std;void solve() {int n, m;cin >> n >> m;vector<int> a(n), b(m);// a 表示服务器算力for (int i = 0; i < n; ++i) cin >> a[i];// b 表示每个任务需要的算力for (int i = 0; i < m; ++i) cin >> b[i];// 从小到大排序sort(a.begin(), a.end());sort(b.begin(), b.end());int ans = 0;for (int i = 0, j = 0; i < m; ++i) {while (j < n && a[j] <= b[i]) {j += 1;}if (j < n) {ans += 1;j += 1;}}cout << ans << "\n";
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;for (int ca = 1; ca <= T; ++ca) {solve();}return 0;
}

// 角度二
#include<bits/stdc++.h>
using namespace std;void solve() {int n, m;cin >> n >> m;vector<int> a(n), b(m);// a 表示服务器算力for (int i = 0; i < n; ++i) cin >> a[i];// b 表示每个任务需要的算力for (int i = 0; i < m; ++i) cin >> b[i];// 从小到大排序sort(a.begin(), a.end());sort(b.begin(), b.end());// 从算力最大的服务器开始，找到一个任务所需算力小于这个服务器的int ans = 0;for (int i = n - 1, j = m - 1; i >= 0; --i) {// 排除所有算力需要大于等于当前服务器算力的任务// 这些任务不可能被完成while (j >= 0 && b[j] >= a[i]) {j -= 1;}// 如果找到一个任务if (j >= 0) {// 答案 + 1ans += 1;// 该任务已被完成j -= 1;}}cout << ans << "\n";
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;for (int ca = 1; ca <= T; ++ca) {solve();}return 0;
}