Codeforces 626E Simple Skewness(暴力枚举+二分)

E. Simple Skewness

time limit per test:3 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

Define the simple skewness of a collection of numbers to be the collection's mean minus its median. You are given a list of n (not necessarily distinct) integers. Find the non-empty subset (with repetition) with the maximum simple skewness.

The mean of a collection is the average of its elements. The median of a collection is its middle element when all of its elements are sorted, or the average of its two middle elements if it has even size.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of elements in the list.

The second line contains n integers xi (0 ≤ xi ≤ 1 000 000) — the ith element of the list.

Output

In the first line, print a single integer k — the size of the subset.

In the second line, print k integers — the elements of the subset in any order.

If there are multiple optimal subsets, print any.

Examples

Input

4
1 2 3 12

Output

3
1 2 12 

Input

4
1 1 2 2

Output

3
1 1 2 

Input

2
1 2

Output

2
1 2

Note

In the first case, the optimal subset is

, which has mean 5, median 2, and simple skewness of 5 - 2 = 3.

In the second case, the optimal subset is

. Note that repetition is allowed.

In the last case, any subset has the same median and mean, so all have simple skewness of 0.

题目链接:http://codeforces.com/contest/626/problem/E

题意

给出n个数的集合,求一个 (平均数-中位数)最大 (偏度最大)的子集,输出子集元素个数和各个元素(任意顺序)。

分析

因为是子集,所以不一定是连续的序列。然后我们有下面几个结论。

1.最大偏度一定≥0

因为一个元素时,偏度为0。

2.最大偏度子集必定有元素个数为奇数个的。

证:

如果当元素个数是偶数2*k时偏度最大,我们证明它去掉一个元素a[k+1]不会更差。

子集里排好序分别是a[i]。除去a[k+1]其它数的平均值为av

新平均值-旧平均值=av-(av+a[k+1])/2=(av-a[k+1])/2

新中位数-旧中位数=a[k]-(a[k]+a[k+1])/2=(a[k]-a[k+1])/2

且有 旧平均值-旧中位数=(av+a[k+1])/2-(a[k]+a[k+1])/2=(av-a[k])/2≥0 (否则不可能偏度最大)

所以有 平均值增量-中位数增量=(av-a[k])/2≥0

所以新的偏度肯定不会更差。

3.平均值先递增后递减

因为是奇数个,所以枚举每个数做中位数,假如左右延伸长度为j,那么要使偏度更大,我们一定是每次选剩下的里面左边最大和右边最大的数。所以剩下的数越来越小,平均值增加得越来越少,而当前平均值越来越大,到某个峰值后平均值就开始减小了。

所以可以用二分法每次取中点和中点旁边一个点判断当前平均值在增加还是减小,增加就往右找,减小就往左找。

顺便吐槽一句:cf测评机不行啊,跑这个跑了大半个小时才跑完!!!

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=200020;
 5 inline int read()
 6 {
 7     int x=0,f=1;
 8     char ch=getchar();
 9     while(ch<'0'||ch>'9')
10     {
11         if(ch=='-')
12             f=-1;
13         ch=getchar();
14     }
15     while(ch>='0'&&ch<='9')
16     {
17         x=x*10+ch-'0';
18         ch=getchar();
19     }
20     return x*f;
21 }
22 int n;
23 ll s[N<<1],a[N<<1];
24 int ansi=1,ansp;
25 double ans;
26 //最大偏度≥0,所以初始值就是只有第一个元素,偏度为0
27 ll sum(int i,int j)
28 {
29     return s[n]-s[n-j]+s[i]-s[i-j-1];
30 }
31 int main()
32 {
33     n=read();
34     for(int i=1;i<=n;i++)
35         cin>>a[i];
36     sort(a+1,a+1+n);
37     for(int i=1;i<=n;i++)
38     {
39         s[i]=s[i-1]+a[i];
40     }
41     for(int i=2;i<n;i++)
42     {
43         int l=1,r=min(i-1,n-i),m;
44         ll s1,s2;
45         while(l<r)
46         {
47             int mid=(l+r)/2;
48             s1=sum(i,mid)*(2*mid+3);
49             s2=sum(i,mid+1)*(2*mid+1);
50             if(s1>s2)
51             {
52                 r=mid;
53             }
54             else
55             {
56                 l=mid+1;
57                 if(s1==s2)
58                     break;
59             }
60         }
61         if(1.0*sum(i,l)/(2*l+1)-a[i]>ans)
62         {
63             ans=1.0*sum(i,l)/(2*l+1)-a[i];
64             ansi=i;
65             ansp=l;
66         }
67     }
68     cout<<ansp*2+1<<endl;
69     cout<<a[ansi]<<" ";
70     for(int i=1;i<=ansp;i++)
71     {
72         cout<<a[ansi-i]<<" "<<a[n-i+1]<<" ";
73     }
74     cout<<endl;
75     return 0;
76 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏钱塘大数据

【干货】十大必须掌握的基础实用算法及其讲解

作者:CSDN大数据 算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下...

2766
来自专栏游戏开发那些事

【随笔】游戏程序开发必知的10大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n logn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事...

883
来自专栏WD学习记录

牛客网 连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候...

842
来自专栏有趣的Python和你

Python数据分析之锁具装箱问题问题重述问题分析建模与求解

1103
来自专栏CDA数据分析师

数据分析师不可不知的10大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较...

2128
来自专栏随笔小哥哥

程序员必须知道的10大基础实用算法及其讲解:排序、查找、搜索和分类等

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

520
来自专栏华章科技

程序员必须知道的10大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,...

872
来自专栏数说工作室

【SAS Says】高级篇:IML(1)

开篇话: 前段时间数说君征原创稿,果真得到了不少牛人的赐稿,比如本文的作者Ansta,作为数说工作室的特约撰稿人,将会承担下“【SAS Says】高级篇” 的写...

3144
来自专栏智能算法

程序员必须知道的十大基础实用算法及其讲解

出自博客园 原文地址:http://kb.cnblogs.com/page/210687/ 算法一:快速排序算法   快速排序是由东尼·霍尔所发展的一种排序算法...

3768
来自专栏郭耀华‘s Blog

剑指offer第七天

30.连续子数组的最大和 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最...

2629

扫码关注云+社区