操作k次最大的最小值

题目描述

给一个序列 a1,a2,…,an。
你可以对这个序列进行操作，每次操作可以选择一个元素，把它加 1，经过不超过 k 次操作之后，希望序列里面的最小值最大。问这个值是多少。
对于 100% 的数据，满足 $1\le n\le 10^5,1\le a_i\le 10^8,0\le k\le 10^{13}1\le n\le 10^5,1\le a\_i\le 10^8,0\le k\le 10^\{13\}$。

思路

$KK$次操作一定是用满的

二分答案
一定存在一个边界值$MM$，满足：
所有数变为$MM$的操作数是的，变为$M+1M+1$的操作数是$>K>K$的

判断边界
最小值：数$MM$一定是$>=1>=1$的
最大值:所有操作都对一个值进行，最大可以到$10^8+10^{13}10^8+10^\{13\}$

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,a[maxn];
ll k;
ll calc(ll x){
	ll res=0;
	for(int i=0;i<n;i++)
		if(a[i]<x) res+=x-a[i];
	return res; 
}
int main()
{
	scanf("%d%lld",&n,&k);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	ll l=1,r=1e14;
	while(l+1<r){
		ll mid=(l+r)/2;
		if(calc(mid)<=k) l=mid;
		else r=mid;
	}
	printf("%lld",l);
	return 0;
}