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.

#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; 
}