看到中位数考虑先把数排序一下
然后有个显然的贪心，一个数增加后一定不能比下一个数大，不然我们直接增加下一个数显然更优
所以初始时的中位数操作后也是中位数
那么我们只要考虑中间再往后怎么加使得答案最大
为了使中位数比较大当然先把中间位置加到和下一个位置一样大，然后为了继续增大又要把后面两个位置增大，然后是后面三个...
所以直接枚举和中间往后第几个即可
设最终答案为 $ans$ ，中间往后一共有 $x$ 个位置一起加，初始时的数列为 $a_i$
那么 $ans*x=(\sum_{i=mid}^{mid+x}a_i)+K$，并且注意 $ans$ 不能超过 $a_{mid+x+1}$
所以最终答案为 $min( \left \lfloor \frac {(\sum_{i=mid}^{mid+x}a_i)+K}{x}\right \rfloor , a_{mid+x+1} )$
注意此时 $a_{n+1}$ 为 $INF$
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7; const ll INF=1e18; ll n,K,a[N]; int main() { n=read(),K=read(); for(int i=1;i<=n;i++) a[i]=read(); sort(a+1,a+n+1); int m=(n+1)/2; a[n+1]=INF; ll sum=0,ans=a[m]; for(int i=m;i<=n;i++) { sum+=a[i]; if((sum+K)/(i-m+1)<a[i]) continue; if((sum+K)/(i-m+1)<=a[i+1]) ans=max(ans,(sum+K)/(i-m+1)); else ans=max(ans,a[i+1]); } printf("%lld\n",ans); return 0; }
Codeforces 1201C. Maximum Median
原文：https://www.cnblogs.com/LLTYYC/p/11597420.html