1 条题解
-
1赵青海 (huhe) LV 7 SU @ 2021-8-7 19:00:37
C++ :
#include <iostream> #include <algorithm> #include <set> using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 100010; int n, m; PII mchs[N], tasks[N]; int main() { while(cin >> n >> m) { for(int i = 0; i < n; i++) cin >> mchs[i].first >> mchs[i].second; for(int i = 0; i < m; i++) cin >> tasks[i].first >> tasks[i].second; sort(mchs, mchs + n); sort(tasks, tasks + m); //从小到大排序 multiset<int> ys; //可以用相同元素 LL cnt = 0, res = 0; for(int i = m - 1, j = n - 1; i >= 0; i--) //从大到小遍历 i枚举任务,j枚举机器 { int x = tasks[i].first, y = tasks[i].second; while(j >= 0 && mchs[j].first >= x) ys.insert(mchs[j --].second); //横坐标大于等于当前任务的机器加入set auto it = ys.lower_bound(y); //>=当前任务y值的最小y if(it != ys.end()) { cnt ++; res += 500 * x + 2 * y; ys.erase(it); // 删掉机器 } } cout << cnt << ' ' << res <<endl; } return 0; }
- 1
信息
- ID
- 38
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 1
- 标签
- 递交数
- 74
- 已通过
- 56
- 上传者