题目链接
给定一个n个数序列，选取一些数，使得这些数的平均数减中位数尽可能大。如有多个结果，随意输出一个。
思路：
首先先上神结论:
要想使平均数-中位数尽可能的大,则选择的数的个数一定为奇数个,偶数个一定不会比他更优.
不太对的证明？
先进行排序 选数时有两种情况，奇数个和偶数个，分别来看，设：
奇数时 u是平均数， n个数 ， x1是中位数 偶数时 ((n*u)+x2)/(n+1)平均数 ,n+1个数， (x1+x2)/2 是中位数 平均数大于中位数 u>x1，偶变奇时 平均数的变化量：(x2-u)/(n+1) ， 中位数变化量：（x2-x1)/2 ，
中位数的变化量大于平均数的变化量。 所以当选偶数个时我们舍弃掉中位数中较大的一个，所得的结果一定比选偶数个优，所以一定选择奇数个数。
PS ：
我们知道选数的个数一定为奇数个之后,就要考虑要怎么求了.
首先可以考虑,当选出的数的个数很少,则平均值-中位数 越来越小,当选取的数很多的时候 平均-中位数也越来越小.
那么二者中间一定存在某个位置有极大值.这就满足了三分的性质,题目也正好要让我们求最大的.所以可以考虑三分.
三分的话,我们还是三分区间然后check.我们枚举每个数来当中位数,然后求平均数.中位数确定了所以我们要让平均值尽量打,那么在中位数左面的数应该尽可能选择靠近中位数的数,在中位数右边的数应该选择尽可能原理中位数的数,以此来求平均值.这个过程可以考虑维护一个前缀和来得到,因为除法会有精度损失,所以我们把最后结果都乘上一个数的个数,转化为整数来做.剩下的就很简单了.
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<set> #include<vector> #include<queue> #include<map> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const ll mod=1e9+7; const int maxn=2e5+10; ll sum[maxn],a[maxn]; int n; ll cal(int len,int pos) { ll res = sum[n] - sum[n-len]+sum[pos]-sum[pos-len-1]; return res; } int main() { while(~scanf("%d",&n)) { sum[0] = 0; ll len = 0,mid = 1,mm = 0; for(int i = 1;i <=n ;i++) scanf("%lld",&a[i]); sort(a+1,a+1+n); for(int i = 1;i <=n ;i++) sum[i] = sum[i-1]+a[i]; for(int i = 2;i <=n-1;i++) { int l=0,r=min(i-1,n-i),lmid,rmid; while(l<=r) { lmid = l + (r-l)/3; rmid = r - (r-l)/3; ll s1 = cal(lmid,i); ll s2 = cal(rmid,i); if(s1*(2*rmid+1) < s2*(2*lmid +1)) l = lmid + 1; else r = rmid - 1; } ll res = cal(l,i) - (2*l+1)*a[i]; if(res*(2*len+1)>mm*(2*l+1)) { mm = res; len = l; mid = i; } } printf("%lld\n",2*len+1); for(int i = mid-len;i <= mid;i++) printf("%lld ",a[i]); for(int i = n-len +1;i <= n;i++) printf("%lld ",a[i]); puts(""); } return 0; } Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
