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 条评论
登录 后参与评论

相关文章

来自专栏郭耀华‘s Blog

剑指offer第七天

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

26990
来自专栏随笔小哥哥

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

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

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

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

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

10530
来自专栏WD学习记录

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

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

11720
来自专栏潇涧技术专栏

Problem: Delete Number Problem

这题可以使用贪心策略,每次从高位向低位数,删除高位比低位数字小的那位上的数字,直到删除了k位之后,得到的数字肯定是最大值。

9620
来自专栏tkokof 的技术,小趣及杂念

Sweet Snippet系列 之 随机选择

  平日工作学习时总会遇到一些令人欣喜的代码段子(Snippet),虽然都很短小,但是其间所含的道理都颇有意味,遂而觉得应该不时的将她们记下,一来算作复习整理,...

12420
来自专栏ml

由判断三一点是否在三角形内部而引发的思考.....

判断一个点是否在三角形里面(包括边界上),这个问题对于许多初学者来说,可谓是一头雾水,如何判断呢? 假如有四个点A(x0,y0),B(x1,y1),C(x2,y...

31080
来自专栏老九学堂

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

最近社群很多的小伙伴们对算法进行了激烈的讨论与学习,今天老九君就给大家介绍一些编程语言里的基础算法,提高小伙伴们的算法知识及编程里对算法的运用。 我们一起来看看...

37450
来自专栏潇涧技术专栏

Python Algorithms - C3 Counting 101

原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法

9840
来自专栏CDA数据分析师

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

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

22380

扫码关注云+社区

领取腾讯云代金券