1.题目思路

首先，拿到题目，我们感到无从下手，感觉题目非常的神秘。

我们首先要思考，庄家的最优策略是什么。

对着样例面壁思索，我们最终发现，庄家如果按照最优策略，对于每种茶包，他一定会拿

B_i - 1

个，因为这样就能让我们刚好凑不齐

B_i

个同类型茶包，如果某种茶包不够

B_i - 1

个，那么就会拿全部茶包（因为即使全拿，我们也不能凑齐）。

如果庄家每种茶包都按照最优方法拿，最终一定会来到一个临界点，只要超过这个临界点，最优方法就会被打破，我们就能凑齐至少一种茶包。

如何打破这个临界点？我们只需要在庄家的最优策略上

+ 1

即可，这样就一定会存在至少一种凑齐的茶包。

这就是一种贪心的做法。

2.贪心的正确性

考虑反证法。

假设庄家使用了一种最优策略，使得有一种茶包没有拿够

B_i - 1

个，那么他一定可以再多拿一些，使得我们的答案更劣（即使得我们声明的

x

更大），这与开始假设的“最优策略”相矛盾，得证。

3.快速查找

然而，只是贪心还是不够的，如果直接暴力，仍然会超时。

此时，由于原数组的元素顺序不会影响结果，考虑将原数组排序，再进行二分查找。每次查找第一个大于等于

B_i

的元素下标。在这个位置之前的所有元素都小于

B_i

，因此可以将他们全部拿走，这部分前缀和计算即可；对于这个位置及之后，元素都大于等于

B_i

，这部分对于每种直接拿

B_i - 1

个即可，设大于等于

B_i

的第一个位置为

l

则公式为

(N-l+1) \times (B_i-1)

。

4.代码

注：代码仅供参考。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int max_n=3e5+2;
long long n,q,a[max_n],b,sum[max_n]; //开 long long！
int main(){
	scanf("%lld %lld",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+n+1); //二分的前提是数组有序
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i]; //前缀和
	}
	for(int z=1;z<=q;z++){
		scanf("%lld",&b);
		int l=lower_bound(a+1,a+n+1,b)-a; //二分查找第一个大于等于 b 的数的位置
		if(l>n){ //没有找到，输出 -1
			puts("-1");
			continue;
		}
		long long ans=0; //计算答案
		ans=sum[l-1]+(n-l+1)*(b-1);
		printf("%lld\n",ans+1);
	}
	return 0;
}

题解：AT_abc418_c [ABC418C] Flush

文章操作