201793模拟赛T2 取数(win)

题目

题解

做法1：

直接暴力枚举每个数是否被选出，计算平均数-中位数，并与当前答案进行比较。复杂度O(2^n)，能过60%的数据。

做法2：

将每个数排序后枚举中位数。

首先，取奇数个数一定更优。容易证明，如果取偶数个数，中位数与平均数相距一定更小。

其次，除中位数以外，数一定尽量往后取，这样中位数不变，平均数增大，才能使答案最大。所以，中位数确定以后，枚举中位数两边数的个数（数都靠后取），计算答案。计算过程可以用前缀和把复杂度降到O(1)。

^{总的复杂度O(n^2+nlog}^{n+n)=O(n^2)，能过75%的数据。}

满分做法：

还是排序后枚举中位数。

注意到题目后的一长段话，由于f(w,l)为关于l的单峰函数，可以用三分法找出最佳的l。复杂度O(nlogn+nlogn+n)=O(nlogn)，能过100%的数据。

代码

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #define N 100005
 4 int n,a[N],b[N];
 5 int min(int a,int b){return a<b?a:b;}
 6 double calc(int i,int l) {//计算平均数-中位数
 7     return (b[i]-b[i-l-1]+b[n]-b[n-l])/(double)((l<<1)+1);
 8 }
 9 int tricalc(int i) {//三分，中位数下标为i
10     int l=0,r=min(i-1,n-i),p,q,t;//l,r为三分区间，p,q为两个点
11     while(l<r) {
12         t=(r-l)/3;
13         p=l+t;q=r-t;
14         if(calc(i,p)>calc(i,q)) r=q-1; else l=p+1;
15     }
16     return l;
17 }
18 int main() {
19     double tmp,ans=0.0;
20     scanf("%d",&n);
21     for(int i=1;i<=n;++i) scanf("%d",a+i);
22     std::sort(a+1,a+n+1);
23     for(int i=1;i<=n;++i) b[i]=a[i]+b[i-1];//前缀和
24     for(int i=1;i<=n;++i) {
25         tmp=calc(i,tricalc(i))-a[i];//三分找出最佳l
26         if(tmp>ans) ans=tmp;
27     }
28     printf("%.2lf",ans);
29     return 0;
30 }

偷看一眼代码

完结撒花+日常%czhou~~~