2017-08-02 23:12:52
writer：pprp
题目大意：给你n个数，从n个数中选取几个数，使平均数和中位数的差值最大，将选取的个数还有选取的数字找出；
算法分析：先枚举，再三分
枚举中位数，可以证明中位数一定是一个，而不是两个组成的。
三分主要用于类似于二次函数的曲线中，有极大或者极小值
代码及分析如下：
#include <iostream> #include <algorithm> #include <stdio.h> #include <cstdlib> using namespace std; typedef long long ll; const ll maxn = 200050; const ll INF = 0x3f3f3f3f; ll a[maxn]; ll sum[maxn];//sum数组是记录了从1到i的总和 int main() { ll n; cin >> n; for(ll i = 1; i <= n ; i++) { scanf("%lld",&a[i]); } sort(a+1,a+1+n); sum[0] = 0; //完成sum的赋值 for(ll i = 1; i <= n; i++) { sum[i] = sum[i - 1] + a[i]; } //对n = 1和 n = 2的情况进行特判 if(n == 1 || n == 2) { printf("1 "); printf("%lld ",a[1]); return 0; } ll l, r; //represent left and right ll m1, m2; //三分之一点处的长度，和三分之二处的长度 ll s1, s2; //分别代表m1/m2时的总和（不包括枚举的点） ll mark_sum = 0, mark_len = 0, mark_mid = 1;//作为标记 ll ssum = 0, len = 0, mid = 1 ; //初始化 //头和尾不可能所以从 2到n-1 for(ll i = 2 ; i <= n - 1 ; i++) { l = 1; r = min(n-i,i-1);//看看左右两边哪个更短，r是长度不是角标 for(ll j = 1; j <= 100; j++)//估计了一个数:100 { m1 = (2 * l + r) / 3; //三分之一点到右端的距离 m2 = (l + 2 * r + 2) / 3;//为了向上取整才加上2，三分之二点到右端的距离 s1 = sum[i] - sum[i - m1 - 1] + sum[n] - sum[n - m1]; s2 = sum[i] - sum[i - m2 - 1] + sum[n] - sum[n - m2]; if(s1 * (2 * m2 + 1) < s2 * (2 * m1 + 1)) //2 * m + 1是总个数，这个比较的是平均值得大小 { l = m1 + 1; //三分转移,从右往左看，从r处往左侧理解 } else { r = m2 - 1; //三分转移 } } ssum = sum[i] - sum[i - l - 1] + sum[n] - sum[n - l] - (2 * l + 1) * a[i]; len = l;//记录长度为len mid = i;//记录下来枚举的点的坐标 if(ssum*(2 * mark_len + 1) > mark_sum * (2 * len + 1))//取最大值 { mark_sum = ssum; mark_len = len; mark_mid = mid; } } //输出个数 cout << mark_len * 2 + 1 << endl; //为了格式 ll flag = 1; for(ll i = mark_mid - mark_len ; i <= mark_mid ; i++) //输出前一半 { if(flag) { flag = 0; printf("%lld",a[i]); } else { printf(" %lld",a[i]); } } //输出后一半 for(ll i = n - mark_len + 1; i <= n ; i++) printf(" %lld",a[i]); printf(" "); return 0; }
很奇怪，一开始用cin ， cout来做就不行，采用printf还有scanf的时候可以，还有要用%lld