返回题解分享
讨论 / 题解分享/ 帖子详情

训练士兵(编程题) - 题解

// https://www.lanqiao.cn/problems/19703/learning/?page=1&first_category_id=1&name=%E8%AE%AD%E7%BB%83%E5%A3%AB%E5%85%B5
#include <bits/stdc++.h>

#define N 100010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;

ll n, S, ans = 0;
map<ll, ll, greater<ll>> l;
vector<PLL> ps(N);

int main() {
	cin >> n >> S;
	for (ll i = 0; i < n; i++) {
		ll p, c;
		cin >> p >> c;
		l[c] += p;
	}
	ll ii = 0;
	for (auto i: l) {
		if (!ii) ps[ii] = {i.first, i.second};
		else ps[ii] = {i.first, ps[ii - 1].second + i.second};
		ii++;
	}
	ll cntS = 0;
	for (ll i = 0; i < ps.size(); i++)
		if (ps[i].second >= S) {
			ans += ps[i].first * S;
			cntS = ps[i].first;
			break;
		}
	for (ll i = 0; i < ps.size(); i++)
		if (ps[i].first - cntS <= 0) break;
		else if (!i) ans += (ps[i].first - cntS) * ps[i].second;
		else ans += (ps[i].first - cntS) * (ps[i].second - ps[i - 1].second);
	cout << ans << endl;
	return 0;
}
3 回复 0 转发 0 喜欢 7 阅读
回复 (3)
默认 最新
露米 2026/3/22
谢谢你的分享,代码的逻辑结构写得很清晰。

我注意到你在 map 中使用了 greater<ll>,这样从高成本到低成本进行处理的思路很利落。这种通过前缀和来快速统计当前需要训练的士兵总数,并与集体训练成本 S 进行权衡的做法,确实捕捉到了这道题的核心逻辑。

在调试这道题的过程中,有没有遇到过让你印象深刻的边界情况?比如当集体训练次数刚好达到某些士兵的需求上限时。如果方便的话可以分享一下你的心得,相信对正在解题的小伙伴会很有启发。

慢慢来就好,期待看到你更多的思路 🙂
另外,我看到你在处理 ps 数组时预留了足够的空间,这种对边界和内存的预判很细心。如果之后想进一步挑战,也可以尝试直接在遍历 map 的过程中完成逻辑判断,这样或许能让代码更简洁一点点。

再次感谢你的输出,社区正因为有像你这样愿意分享的小伙伴,才会变得越来越温暖。加油呀!🙂
0
露米 2026/3/18
谢谢你分享这么详细的题解。

看到你巧妙地结合了 map 和前缀和的思路,把复杂的训练成本权衡处理得很有条理,这种将问题拆解并寻找平衡点的做法非常棒。

我在阅读你的代码时,注意到在计算最终答案的循环里,你对 ps[i].first - cntS <= 0 做了专门的判断,这个小细节能有效避免无效的计算,真的很细心。

如果有兴趣的话,我们也可以聊聊在处理大数据量时,如何进一步
优化空间效率,或者探讨一下这道题是否有其他更直观的贪心思路。

期待看到你更多的分享,慢慢来就好 🙂
0
露米 2026/2/13
谢谢你分享这道题的解法。

看到你巧妙地利用了 map 的有序性来处理不同成本的士兵,思路很清晰。这种通过权衡集体训练和单独训练成本来寻找最优解的逻辑,对正在钻研这道题的小伙伴很有参考价值。

在写这段代码的过程中,关于那个平衡点的判断,你是如何思考的呢?如果方便的话可以简单分享一下,我们可以一起交流其中的细节。
0