「AtCoder abc144E」Gluttony

题意：给定两个数 $n,k$ 和两个序列 $a[],f[]$，可以有 $k$ 次操作把 $a[]$ 中一个元素减 $1$，然后把 $a[]$ 和 $f[]$ 两两配对，求乘积最大的那个数的最小值。

最大值最小，二分答案。

很明显，要让乘积尽量小，那么我们把 $a$ 数组从小到大排序，再将 $f$ 数组从大到小排序，这样能使乘积尽量平均，从而使乘积最大最小。

然后我们直接二分乘积最大的数为 $x$，然后检查每个 $\frac{x}{f}$ 是否大于 $a$，把每个多的加起来，看看是否能达到 $k$，即判断 $k$ 次之内能否使 $a\times f\leq x$。

然后直接输出答案即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,k,tot;
long long a[201010],b[201010],f[201010];
long long cmp(long long a,long long b)
{
	return a>b;
}
bool check(long long x)
{
	long long p=0;
	for(int i=1;i<=n;i++)
		b[i]=x/f[i];//求出当答案为x时应该对应的a数组
	for(int i=1;i<=n;i++)
		p+=max(0ll,a[i]-b[i]);//求出差值
	if(p<=k)//判断这些能否改变
		return true;
	return false;
}
int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		tot+=a[i];
	}
	for(int i=1;i<=n;i++)
		scanf("%lld",&f[i]);
	if(tot<=k)
	{
		printf("0");
		return 0;
	}
	sort(a+1,a+n+1);
	sort(f+1,f+n+1,cmp);
	long long l=1,r=1e12,mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(check(mid))
			r=mid;
		else
			l=mid+1;
	}
	printf("%lld",l);
	return 0;
}