Tenka1 Programmer Contest 2018 C – Align 题解【贪心】【数学】

作者: wjyyy 分类: 数列,数学,解题报告,贪心 发布时间: 2018-10-28 16:58

点击量:215

 

    感觉这个贪心证明挺不错的。

 

Problem Statement

You are given \(N\) integers; the \(i\)-th of them is \(A_i\). Find the maximum possible sum of the absolute differences between the adjacent elements after arranging these integers in a row in any order you like.

Constraints

\(2\le N\le 10^5\)

\(1\le A_i\le 10^9\)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A1
:
AN

Output

Print the maximum possible sum of the absolute differences between the adjacent elements after arranging the given integers in a row in any order you like.

Sample Input 1

5
6
8
1
2
3

Sample Output 1

21

When the integers are arranged as \(3,8,1,6,2\), the sum of the absolute differences between the adjacent elements is \(|3−8|+|8−1|+|1−6|+|6−2|=21\). This is the maximum possible sum.

Sample Input 2

6
3
1
4
1
5
9

Sample Output 2

25

Sample Input 3

3
5
5
1

Sample Output 3

8

题意:

    给定\(n\)个数,你可以任意排列它们,求排列后能产生的相邻两项差的和最大值是多少。

题解:

    做题的时候想到了这个比较对的贪心,但是只是感觉上是对的,其实我并不会证。大致上是枚举两种情况。

    第一种是先把最大的放中间,接着在它两边放上两个没放过的最小的,尽量使左边小,产生一个长为\(3\)的序列。接着在序列的两端放上两个没放过的最大的,也是尽量使左边大,这样“小大小”交替着放,直到没有元素;第二种是先把最小的放中间,然后“大小大”交替放,直到没有元素。枚举这两种情况的原因是看到样例1中间放最大也合法,中间放最小也合法,但是样例3中间只能放最小的。

    实际上这个贪心有一个严谨证明。

    首先在序列中一定不会出现三个这样的元素:\(A_{i-1}\le A_i\le A_{i+1}\),因为如果把\(A_i\)抽出来放在序列最后,\(\{A_{i-1},A_{i+1}\}\)这两个元素就能做出之前\(\{A_{i-1},A_i,A_{i+1}\}\)做出的贡献,当然把\(A_i\)放最后能产生更多的贡献。因此这个序列一定是大小交替的,满足\(A_{i-1}\ge A_i\le A_{i+1}\)或者\(A_{i-1}\le A_i\ge A_{i+1}\)。

    因为两种情况是对称的,所以先只考虑一种情况,假设\(A_1\le A_2\ge A_3\le A_4\ge \dots \),那么产生的贡献就是\((A_2-A_1)+(A_2-A_3)+(A_4-A_3)+(A_4-A_5)+\dots\)。括号拆开就是\(-A_1+2A_2-2A_3+2A_4-\dots \pm A_{n}\),可以发现,每个元素做出的贡献可能是\(\{-2,-1,1,2\}\),那么为了保证最大,我们当然要把数值较大的元素放在\(2\),最小的放在\(-2\),但是一定要记着给左右两边留一个\(\pm 1\)。对于另一种情况,不同的就是两端点的符号,因此对于\(\{-2,-1,1,2\}\)计数,看看每种状态需要多少个元素,排序后贪心就可以了。

    然后我们还是要做两种情况,我是直接模拟最优解然后统计的,上面这样貌似更加优秀。时间复杂度都是\(O(n\log n)\)。

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::sort;
int Abs(int x)
{
    return x>0?x:(-x);
}
int a[100100];
int b[100100],t1=50000,t2=50002;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    b[50001]=a[1];
    for(int l=2,r=n;l<=r;)
    {
        b[t1--]=a[r--];
        if(l<r)
            b[t2++]=a[r--];
        if(l<r)
            b[t1--]=a[l++];
        if(l<r)
            b[t2++]=a[l++];
    }
    long long sum=0;
    for(int i=t1+2;i<t2;++i)
        sum+=Abs(b[i]-b[i-1]);
    long long ans=sum;
    t1=50000,t2=50002;
    b[50001]=a[n];
    for(int l=1,r=n-1;l<=r;)
    {
        b[t1--]=a[l++];
        if(l<r)
            b[t2++]=a[l++];
        if(l<r)
            b[t1--]=a[r--];
        if(l<r)
            b[t2++]=a[r--];
    }
    sum=0;
    for(int i=t1+2;i<t2;++i)
        sum+=Abs(b[i]-b[i-1]);
    printf("%lld\n",ans>sum?ans:sum);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */