上海计算机学会2024年10月月赛C++乙组T4购物
发布时间
阅读量：
阅读量
购物
内存限制: 256 Mb时间限制: 1000 ms
题目描述
有n位顾客各自打算购买一台个人计算机，在商店中可供选择的共有m台不同型号的设备。每台设备都有不同的配置参数与定价标准：第i台计算机的价格定位xi元人民币（人民币符号在中文环境下通常省略），其核心性能指标则为yi单位（单位标识需根据具体情况确定）。每位顾客对所购设备提出了明确的技术规格要求：即在价格方面不低于ai元人民币，在性能指标方面则至少达到yi单位的标准。
为了解决资源分配问题，请合理配置资源以满足每位顾客的需求，并确保总成本最低
输入格式
- 第一行：一对整数值代表n和m。
- 接下来的n行：每行包含两组数值ai和bi。
- 之后的m个块：每块包含两组数值xi和yi。
输出格式
- 如果可以分配，输出售价之和的最小值，否则输出
No
数据范围
- 对于 30% 的数据，n,m≤500
- 对于 60% 的数据，n,m≤5000
- 对于 100% 的数据，1≤n,m≤200,000
- 1≤ai,bi≤1,000,000,000
- 1≤xi,yi≤1,000,000,000
样例数据
输入:
2 3
1 2
2 1
3 3
1 1
2 3
输出:
5
解析：贪心法采用当前电脑包含所有满足价格小于其价格的需求中性能最强的那个方法，请参见代码：
#include <bits/stdc++.h>
using namespace std;
int n, m;
struct node {
int ax, by;
};
multiset <int> s;//使用multiset保存价格需求低于当前电脑价格的需求
node a[200005];//保存需求
node b[200005];//保存电脑价格和性能
bool cmp(node x, node y) {//按价格排序，价格相同的性能低的排前面
if (x.ax == y.ax) return x.by < y.by;
return x.ax < y.ax;
}
long long ans = 0;//答案
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i].ax >> a[i].by;
}
for(int i = 1; i <= m; i++) {
cin >> b[i].ax >> b[i].by;
}
sort(b + 1, b + m + 1, cmp);//排序
sort(a + 1, a + n + 1, cmp);//排序
int j = 1;
for(int i = 1; i <= m; i++) {//枚举每一台电脑
//找出所有价格需求低于当前电脑的需求，并把其需求性能加入multiset
while (j <= n && a[j].ax <= b[i].ax) {
s.insert(a[j].by);
j++;
}
//如果没需求，继续下一台电脑
if (s.size() == 0) continue;
multiset <int>::iterator it;
//找到那个大于电脑性能需求的最小的那个需求
it = s.upper_bound(b[i].by);
//如果是第一个，则没有需求性能小于当前电脑的需求，继续下一台电脑
if (it == s.begin()) continue;
//前一个，即性能需求小于等于电脑性能的需求
it--;
if (*it <= b[i].by) {//若满足需求
s.erase(it);//删除需求
ans += b[i].ax;//记录花费
}
}
//若还有需求没有加入set，则表示有价格需求未被满足
//若multiset中还有需求未被满足
if (j <= n || s.size() != 0) {
cout << "No";//输出no
} else {//否则，输出花费
cout << ans;
}
return 0;
}全部评论 (0)
还没有任何评论哟~