[CodeForces]1671.C Dolce Vita（贪心 + 二分 + 容斥原理）

题目传送门：Problem - C - Codeforces

题目大意

有N个店，每天有X元，每个店 i 每日限购1件，第一天价格为 ai。每个店每天都涨价1元（第一天是原价）。多组测试用例。

思路

买东西嘛，肯定是越便宜越好（Greedy贪心）。所以先将所有价格排序，在进行一次前缀和，现在第i天购买前i个店的商品价格为a[i] + i。

这时候观察一下数据范围，N <= 2e6，所以可以遍历每前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 + 10;
int a[maxn];

int bs(int k, int N,int X)//购买总价格为k的天数 
{
	int l = -1,r = X + 1;
	while(l + 1 != r)
	{
		int mid = (l + r) / 2;
		if(a[k] + k * mid <= X)l = mid;
		else r = mid;
	}
	return r;
}

void solve()
{
	int N, X;cin >> N >> X;//N个店，每天X元
	for(int i = 1;i <= N; ++ i)scanf("%lld", a + i);
	sort(a + 1,a + 1 + N); 
	for(int i = 1;i <= N; ++ i)a[i] += a[i - 1];
	int ans = 0;
	for(int i = 1;i <= N; ++ i)ans += bs(i, N, X);
	printf("%lld\n",ans);
}

signed main()
{
	int _;cin >> _;
	while(_ --)solve();
	return 0;
}