Radical

用户名：dotcpp0602299

访问量：689

签　名：

等　　级
排　　名	3624
经　　验	1860
参赛次数	0
文章发表	10
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2024年第十五届C/C++大学A组省赛真题-训练士兵
浏览：36

蓝桥杯2024年第十五届省赛真题-团建
浏览：64

蓝桥杯2024年第十五届省赛真题-成绩统计
浏览：50

你可能喜欢

蓝桥杯2024年第十五届C/C++大学A组省赛真题-训练士兵

　　作者: Radical　　　　发表时间：2024-10-03 12:02:11 浏览：36　|　评论：0　

**题目描述**

在蓝桥王国中，有 n 名士兵，这些士兵需要接受一系列特殊的训练，以提升他们的战斗技能。对于第 i 名士兵来说，进行一次训练所需的成本为 pi 枚金币，而要想成为顶尖战士，他至少需要进行 ci 次训练。

为了确保训练的高效性，王国推出了一种组团训练的方案。该方案包含每位士兵所需的一次训练，且总共只需支付 S 枚金币（组团训练方案可以多次购买，即士兵可以进行多次组团训练）。

作为训练指挥官，请你计算出最少需要花费多少金币，才能使得所有的士兵都成为顶尖战士？

**输入格式**
输入的第一行包含两个整数 n 和 S ，用一个空格分隔，表示士兵的数量和进行一次组团训练所需的金币数。接下来的 n 行，每行包含两个整数 pi 和 ci ，用一个空格分隔，表示第 i 名士兵进行一次训练的金币成本和要成为顶尖战士所需的训练次数。
输出格式
输出一行包含一个整数，表示使所有士兵成为顶尖战士所需的最少金币数。

**样例输入**

3 6
5 2
2 4
3 2

**样例输出**

**提示**

【样例说明】

花费金币最少的训练方式为：进行 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。

#include <bits/stdc++.h>
    
    #define ll long long 
    using namespace std;
    
    struct A {
    	ll p, c;
    }a[100010];//p是训练一次所需金币，c是该士兵所需训练次数
    
    bool is(A a, A b)
    {
    	return a.c < b.c;
    }
    
    int main()
    {
    	ll n, S,ans =0,total_p=0,total_c=0;//total_p为金币计数器，用来计算当前仍然需要训练的士兵全部训练一次需要多少金币，将其与组团训练所需金币S进行比较；total_c为组团训练次数计数器，用来和士兵所需训练次数a[i].c作比较，判断该士兵是否需要继续训练。
    	cin >> n >> S;
    	for (int i = 1; i <= n; i++)
    	{
    		cin >> a[i].p >> a[i].c;
    		total_p += a[i].p;//一开始，全部训练一次的价格
    	}
    	sort(a + 1, a + n + 1, is);//从低到高排序，升序排列，这步是必要的
    	for (int i = 1; i <= n; i++)
    	{
    		if (total_c >= a[i].c)//如果已组团训练次数total_c和这个士兵所需的次数a[i].c相等或更多
    		{
    			total_p -= a[i].p;//那么这个士兵已经不需要训练，全部训练一次的价格total_p就需要减掉这个士兵训练一次的价格a[i].p
    			continue;//那么就无需判断这个士兵究竟需要哪种训练方案，直接开始下一个
    		}
    
			//判断究竟是组团训练还是单独训练
    		if (total_p > S)//如果组团训练比全部自己训练一次相比起来更合适
    		{
    			ans += (a[i].c - total_c) * S;//那么所需金币数量ans就加上（第i名士兵仍旧所需的组团训练次数乘组团训练一次的费用S）（而第i名士兵仍旧所需的组团训练次数等于该士兵原本所需次数a[i].c减去已进行的组团训练次数total_c）。由于我们已经在第24行将士兵按照所需训练次数c升序排列，故可以这么做
    			total_c = a[i].c;//由于升序排列，总训练次数必定等于第i名士兵所需训练次数
    		}
    		else//如果组团训练反而不合适
    		{
    			ans += (a[i].c-total_c)*a[i].p;//那么ans就加上仍旧所需的训练次数乘单独训练一次的费用a[i].p
    		}
    		total_p -= a[i].p;//由于我们已经把第i名士兵训练完成（不管是上面哪个途径），所以需要将全部训练一次的价格total_p减去第i名士兵单独训练一次的价格a[i].p
    	}
    	cout << ans;
    
    }

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Radical

TA的其他文章

你可能喜欢

C二级辅导-公约公倍（C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-同因查找（C语言代码）

弟弟的作业（C++代码）

蓝桥杯2024年第十五届C/C++大学A组省赛真题-训练士兵

评论区

精彩推荐

矩形面积交（Java代码）

C语言训练-素数问题（C语言代码）

printf基础练习2 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

1126题解

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C二级辅导-等差数列（C语言代码）

蛇行矩阵（C语言代码）

敲七（C++代码）

Radical

TA的其他文章

你可能喜欢

C二级辅导-公约公倍 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-同因查找 （C语言代码）

弟弟的作业 （C++代码）

蓝桥杯2024年第十五届C/C++大学A组省赛真题-训练士兵

评论区

精彩推荐

矩形面积交 （Java代码）

C语言训练-素数问题 （C语言代码）

printf基础练习2 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

1126题解

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C二级辅导-等差数列 （C语言代码）

蛇行矩阵 （C语言代码）

敲七 （C++代码）

C二级辅导-公约公倍（C语言代码）

C二级辅导-同因查找（C语言代码）

弟弟的作业（C++代码）

　　评论区

矩形面积交（Java代码）

C语言训练-素数问题（C语言代码）

C二级辅导-等差数列（C语言代码）

蛇行矩阵（C语言代码）

敲七（C++代码）