2024年蓝桥杯 训练士兵 贪默算法
题目形貌在蓝桥王国中，有 n 名士兵，这些士兵需要担当一系列特别的训练，以提升他们的战斗技能。对于第 i 名士兵来说，举行一次训练所需的成本为 pi 枚金币，而要想成为顶尖兵士，他至少需要举行 ci 次训练。
为了确保训练的高效性，王国推出了一种组团训练的方案。该方案包含每位士兵所需的一次训练，且总共只需支付 S 枚金币（组团训练方案可以多次购买，即士兵可以举行多次组团训练）。
作为训练指挥官，请你盘算出最少需要耗费多少金币，才气使得所有的士兵都成为顶尖兵士？
输入格式
输入的第一行包含两个整数 n 和 S ，用一个空格分隔，表现士兵的数量和举行一次组团训练所需的金币数。接下来的 n 行，每行包含两个整数 pi 和 ci ，用一个空格分隔，表现第 i 名士兵举行一次训练的金币成本和要成为顶尖兵士所需的训练次数。
输出格式
输出一行包含一个整数，表现使所有士兵成为顶尖兵士所需的最少金币数。
样例输入
复制
3 6
5 2
2 4
3 2
样例输出
复制
16
提示
【样例说明】
耗费金币最少的训练方式为：举行 2 次组团训练，耗费 2 × 6 = 12 枚金币，此时士兵 1, 3 已成为顶尖兵士；再耗费 4 枚金币，让士兵 2 举行两次训练，成为顶尖兵士。总耗费为 12 + 4 =
16
。
【评测用例规模与约定】
对于 40% 的评测用例，1 ≤ n ≤ 103，1 ≤ pi, ci ≤ 105，1 ≤ S ≤ 107。
对于所有评测用例，1 ≤ n ≤ 105，1 ≤ pi, ci ≤ 106，1 ≤ S ≤ 1010。
千万留意数的范围！！long long int!!
代码1：
#include <bits/stdc++.h>
#define MX 100005
using namespace std;
struct soldier { //士兵布局体
long long int p;
long long int c;
} d;
bool cmp(soldier p,soldier q) {//将次数举行排序
return p.c < q.c;
}
int main() {
long long int n,s,cnt = 0,sum = 0;
cin>>n>>s;
for(long long int i = 1; i <= n; i++) {
cin>>d.p>>d.c;
sum += d.p;
}
sort(d+1,d+1+n,cmp);
long long int ant = 0;
for(int i = 1;i <= n;i++)
{
if(sum >= s)//贪心分情况讨论
{
cnt = cnt + (d.c - ant)*s;
sum = sum - d.p;
ant = ant + (d.c - ant);
}
else{
cnt += (d.c - ant)*d.p;
}
}
cout<<cnt<<endl;
return 0;
}
代码2：
#include <bits/stdc++.h>
#define MX 100005
using namespace std;
struct soldier{
long long int p;
long long int c;
}d;
bool cmp(soldier p,soldier q)
{
return p.c < q.c;
}
int main() {
long long int n,s,cnt = 0,sum = 0;//cnt记载耗费，sum记载每个士兵训练一次的费用和
cin>>n>>s;
for(long long int i = 1;i <= n;i++)
{
cin>>d.p>>d.c;
sum += d.p;//费用和
}
sort(d+1,d+1+n,cmp);
long long int ant = 1;//ant记载数组序号
while(sum >= s)
{
cnt = cnt + (d.c - cnt);
sum = sum - d.p;
ant++;
}
long long int t;
t = cnt;
cnt *= s;
for(long long int i = ant;i <= n;i++)
{
cnt += (d.c - t)*d.p;//减去已经训练的次数
}
cout<<cnt<<endl;
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]