题目传送门:Problem - C - Codeforces
题目大意
有N个店,每天有X元,每个店 i 每日限购1件,第一天价格为 ai。每个店每天都涨价1元(第一天是原价)。问最终一共最多可以买多少个东西。多组测试用例。
思路
买东西嘛,肯定是越便宜越好(Greedy贪心)。所以先将所有价格排序,在进行一次前缀和,现在第i天购买前j个店的所有商品总价为prefix[j] + i * j。
这时候观察一下数据范围,N <= 2e6,所以可以遍历每前i个店,在固定至少买了i个商品的情况下,通过二分搜索求最多有多少天能至少买i个商品,得到bs[i] = “买的东西 >= i的天数”。
那么恰好购买n个东西的天数 = bs[n] - bs[n + 1]。(容斥原理)
那么答案就是n * bs[n] + (n - 1) * (bs[n - 1] - bs[n]) + ... + 2 * (bs[2] - bs[3]) + bs[1] - bs[2]
整理一下就是bs[1] + bs[2] + ... + bs[n]。
直接记录一下和就好了。
代码
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 2e5 + 9; int N, X, a[maxn], prefix[maxn]; int foo(int k)//求最多有多少天可以至少买k个东西 { //右边界位X + 1,不可能买X天以后的东西,因为价格必定大于等于X元 int l = 0, r = X + 1; while(l + 1 != r) { int mid = (l + r) >> 1; //第mid天买前k个商品的总价 = prefix[k] + k * (mid - 1) if(prefix[k] + k * (mid - 1) <= X)l = mid; else r = mid; } return l; } void solve() { cin >> N >> X; for(int i = 1;i <= N; ++ i)cin >> a[i]; sort(a + 1,a + 1 + N); for(int i = 1;i <= N; ++ i)prefix[i] = prefix[i - 1] + a[i]; int ans = 0; for(int i = 1;i <= N; ++ i)ans += foo(i); cout << ans << '\n'; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _;cin >> _; while(_ --)solve(); return 0; }
Comments NOTHING