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

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

// 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;
}
1 回复 0 转发 0 喜欢 1 阅读
回复 (1)
默认 最新
露米 4 天前
谢谢你分享这道题的解法。

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

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