本文主要是介绍Codeforces-1671 C: Dolce Vita,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Codeforces-1671 C: Dolce Vita
题目链接: Codeforces-1671 C: Dolce Vita
题目
题目截图
样例描述
题目大意
给定一个长度为 n n n 的数组 a i a_i ai,代表 n n n 个商店在第一天卖的糖果价格,在之后每过一天,每个商店糖果的价格就会 + 1 +1 +1。每个商店每天只卖一包糖果。每天给定资金 x x x,去买糖果,求最终能够最多买多少包糖果。
题目解析
显然贪心来讲,我们每天买糖果都会从售价最少的商店进行购买,之后是第二小的,以此类推。因此,解题的第一步是将 a i a_i ai 从小到大排序。为了方便计算,设 p i p_i pi 代表第 1 ⋯ i 1 \cdots i 1⋯i 位的前缀和。
由于可能的天数较多,我们可以换一个角度,从购买糖果的数量入手遍历。对于已经排好序的 a i a_i ai,设能够购买 1 ⋯ i 1 \cdots i 1⋯i 的天数为 k i k_i ki,那么 ( a 1 + k i − 1 ) + ( a 2 + k i − 1 ) + ⋯ + ( a i + k i − 1 ) ≤ x (a_1 + k_i-1) + (a_2 + k_i-1) + \cdots + (a_i + k_i-1) \le x (a1+ki−1)+(a2+ki−1)+⋯+(ai+ki−1)≤x 可以推出 p i + i ∗ k i ≤ x + i p_i + i * k_i \le x + i pi+i∗ki≤x+i 得到最大天数为 k i = ⌊ ( x − p i ) / i ⌋ + 1 k_i = \lfloor (x - p_i) / i \rfloor + 1 ki=⌊(x−pi)/i⌋+1,加一是因为第一天是从 0 0 0 开始的。
那么正好买 i i i 包糖果的天数为 k i − k i − 1 k_i - k _{i-1} ki−ki−1,即对应的结果贡献 i ∗ ( k i − k i − 1 ) i * (k_i - k_{i-1}) i∗(ki−ki−1)。如此,我们遍历 i i i,将结果累积进答案即可。
Code
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int maxn = 2e5 + 7;
int a[maxn];int main() {int t, n, x;cin >> t;while(t--) {cin >> n >> x;LL ans = 0, p = 0;for(int i=1; i<=n; ++i)cin >> a[i], p += a[i];sort(a+1, a+n+1);for(int i = n, pk = -1, nk = -1; i>=1; p -= a[i], --i) {if(x < p) continue;if(pk == -1) pk = (x - p) / i, ans = 1ll * (pk + 1) * i; else {nk = (x - p) / i;ans += (nk - pk) * i;pk = nk;}}cout << ans << endl;}return 0;
}
这篇关于Codeforces-1671 C: Dolce Vita的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!