526互联

Educational Codeforces Round 130 (Rated for Div. 2) B. Promo

发布时间 2023-09-10 20:48:50作者: zsxuan

有 \(n\) 件商品，第 \(i\) 件的价格是 \(p_i\) ，若买至少 \(x\) 件商品，则其中最便宜的 \(y\) 件免费。给 \(q\) 个询问，每次给出 \(x, y\) ，回答最多能免费的价值。

按大到小排序，求前缀和 \(S_{i}\) 表示买前 \(i\) 件商品需要的开销。

答案为 \(S_{x} - S_{x - y}\) 。

view 
#include <bits/stdc++.h>
void solve() {
	int n, q; std::cin >> n >> q;
	std::vector<long long> a(n+1);
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	std::sort(a.begin() + 1, a.end(), std::greater<long long>() );
	for (int i = 1; i <= n; i++) a[i] += a[i - 1];
	for (int i = 0; i < q; i++) {
		int x, y; std::cin >> x >> y;
		std::cout << a[x] - a[x - y] << '\n';
	}
}
signed main() {
	int _ = 1; //std::cin >> _;
	while (_--) solve();
	return 0;
}