蓝桥杯2024年第十五届省赛A组-训练士兵

题目描述

在蓝桥王国中，有 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 ≤ 10^3，1 ≤ pi, ci ≤ 10^5，1 ≤ S ≤ 10^7。

对于所有评测用例，1 ≤ n ≤ 10^5，1 ≤ pi, ci ≤ 10^6，1 ≤ S ≤ 10^10。

整体思路

考虑贪心思想，如果当前所有仍需要继续训练的士兵单独训练一次所需的金币总和total小于一次组团训练所需的金币数S，就使用组团训练，否则当前士兵剩余训练次数全部单独训练。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

typedef struct soldier
{
	int cost;
	int cnt;
}soldier;

class MyCompare
{
public:
	bool operator()(soldier a, soldier b)
	{
		return a.cnt < b.cnt;
	}
};

signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, S;
	cin >> n >> S;
	
	vector<soldier> v(n);
	int total = 0; // 还需训练的士兵单独训练一次需要的金币之和 
	for(int i = 0; i < n; i++)
	{
		cin >> v[i].cost >> v[i].cnt;
		total += v[i].cost;
	}
	sort(v.begin(), v.end(), MyCompare());
	
	int res = 0, sum = 0; // 花费的金币总数；团体训练次数 
	for(int i = 0; i < n; i++)
	{
		if(total >= S)
		{
			res += (v[i].cnt - sum) * S;
			total -= v[i].cost;
			sum += v[i].cnt - sum;
		}
		else
		{
			res += (v[i].cnt - sum) * v[i].cost;
			total -= v[i].cost;
		}
	}
	cout << res << endl;
	return 0;
}

具体步骤

1. 读入数据后按照训练次数从小到大排序，保证训练次数少的都先进行团体训练。

2. 遍历每一位士兵，如果还需要训练的士兵单独训练一次所需要的金币之和total大于等于组团训练一次所需要的金币S，则将当前士兵剩余的训练次数v[i].cnt - sum全部进行组团训练（因为在将当前士兵剩余训练次数训练完之前，total永远小于S）【剩余训练次数可能为零，即当前士兵所需训练次数与上一个士兵相同】，并让还需要训练的士兵单独训练一次所需要的金币之和total减去这个士兵训练一次的花费v[i].cnt（这个士兵已经训练完了），组团训练次数sum加上当前士兵剩余训练次数。

3. 否则将当前士兵剩余训练次数全部进行单独训练，让还需要训练的士兵单独训练一次所需要的金币之和减去这个士兵训练一次的花费。