上海计算机学会2024年5月月赛C++乙组T3对折券
发布时间
阅读量：
阅读量
对折券
内存限制: 256 Mb时间限制: 1000 ms
题目描述
小爱需要将 n 件商品全部买回家，其中第 i 件商品的价格为 ai。
小爱有 m 张对折券，对每件商品，可以使用任意多张对折券，效果是叠加的。若一件商品原价是 A，对该商品使用 k 张对折券后，则该商品的价格将变成 
。其中 ⌊⌋是向下取整的意思。
请计算应该如何分配这些对折券才能使得打折后的商品总价之和变得最小。
输入格式
- 第一行：两个整数表示 n 与 m
- 第二行：n 个整数 a1,a2,…,an 表示各个商品的原价
输出格式
- 单个整数表示答案
数据范围
- 30% 的数据，1≤n≤10，1≤m≤10
- 60% 的数据，1≤n≤500，1≤m≤500
- 100% 的数据，1≤n≤200,000，1≤m≤200,000
- 1≤ai≤1,000,000,000
样例数据
输入:
3 2
50 100 300
输出:
225
说明:
全部同在300上
解析：贪心算法，对折券用在最贵的商品（含打折后价格）上 ，使用优先队列（大根堆）保存商品价格，对最贵的使用对折券，详见代码：
#include <bits/stdc++.h>
using namespace std;
int n,m;
int x;
priority_queue <int> pq;//大根堆
long long ans=0;
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>x;
pq.push(x);
}
for(int i=1;i<=m;i++){
x=pq.top();
pq.pop();
pq.push(x/2);
}
while(!pq.empty()){
ans+=pq.top();
pq.pop();
}
cout<<ans;
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~