题解：AT_abc418_c [ABC418C] Flush

思路

首先，这个商人要尽可能的让你输，就会尽可能平均的取出每一个味道的茶包，所以，就要求出每一个茶包都正好取出 $\min(a_i,b-1)$ 个，然后把这些求和后再加一，效率是 $O(nm)$ ，很明显，炸了。

未AC的Code

#include<bits/stdc++.h>
using namespace std;
long long n,m,maxn,s[3000005],a[3000005];
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
        cin>>a[i],maxn=max(maxn,a[i]);
	while(m--){
		long long x;
		cin>>x;
		if(x>maxn) {
			puts("-1");
			continue;
		}
        int ans=0;
		for(int i=0;i<n;i++){
            ans+=min(x-1,a[i]);
        }
        cout<<ans+1<<'\n';
	}
	return 0;
}

优化

其实这一看到求和，就可以用前缀和，然后使用 STL 自带的二分函数 lower_bound 求出第一个大于等于 $b$ 的数，设这个数为 $pos$ ，使用前 $pos$ 种口味的茶包总数也就是 $s_i$ ，与后面剩下的口味中每种口味至少取 $x-1$ 个茶包的总数相加，最后加一，确保至少再取一个茶包来能有 $b$ 个同口味的茶包。

AC Code

接下来显出本蒟蒻的代码吧。

#include<bits/stdc++.h>
using namespace std;
long long n,m,maxn,s[3000005],a[3000005];//不开____见祖宗。
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)//别问为什么下表要从零开始，布吉岛为什么从一开始过不了。
      cin>>a[i],maxn=max(maxn,a[i]);
	sort(a,a+n);//排序，因为要使用二分查找。
	for(int i=0;i<n;i++) s[i+1]=s[i]+a[i];//求前缀和。
	while(m--){
		long long x;
		cin>>x;
		if(x>maxn){//判断是否可行。
			puts("-1");
			continue;
		}
		int pos=lower_bound(a,a+n,x)-a;//计算pos。
		cout<<s[pos]+(n-pos)*(x-1)+1<<endl;
	}
  return 0;
}

管理大大求过。