Codeforces Round #727 (Div. 2)D. PriceFixed
给N个pairs, 里面第一个数字是需要买几个, 第二个数字是买多少个后可以有优惠价格. 问花多少钱能买够所有需要买的物品.
因为每个物品价格都是一样的,相当于二元店, 买够第一个数字就变成了一元店. 那么我们想花最少钱, 肯定要买最多的打折物品, 但是打折物品需要买够两元的物品才能买, 所以我们按照从小到大的顺序排序好打折物品需要买多少才能买. 然后我们设买够n个物品后, 可以开始买打折物品, 因为我们知道如果买n个可以, 那么买n+1也可以, 所以问题转化成为如何找到n的lower_bound. 这里用二分查找,
方法check就是验证是否存在n个打折物品的可能. 验证方法如下, 假设total是一共要买的物品, 我们知道total-n, 就是没有当前状态下没有打折的物品的数量. 那么我们从最少的需要物品数量就可以买打折物品的物品开始, 如果当前物品的需要购买数量已经大于total-n, 就证明当前这个不能拿了, 于是我们因为拿不到n个物品, 所以return false. 如果当前物品的需要购买数量小于等于total-n, 就证明当前这个可以拿, 我们把它加进来变成total-n+A[i].first, 然后n -= A[i].first, 这样一直找下去, 直到n==0.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include "bits/stdc++.h" using namespace std; #define fr ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define pb push_back; typedef int64_t ll; typedef pair<ll, ll> pll; int main() { fr; ll N; cin >> N; pll A[N]; ll total = 0; for(int i = 1; i <= N; i++) { cin >> A[i].second >> A[i].first; total += A[i].second; } sort(A + 1, A + N + 1); ll left = 0; ll right = total; ll res = 0; auto check = [&](ll n) -> bool { ll cur = total - n; // n is the number of discounted items, cur is the items wit origal price for(int i = 1; i <= N; i++) { if (A[i].first > cur) { return false; } ll taken = min(A[i].second, n); // buy all A[i] in discounted price cur += taken; n -= taken; if(n == 0)// we found all available n return true; } return true; }; while (left < right) { ll mid = left + (right - left) / 2; if (check(mid)) { left = mid + 1; res = mid; } else { right = mid; } } cout << 2 * total - res << endl; return 0; } |