Tenka1 Programmer Contest 2018 C – Align 题解【贪心】【数学】
点击量: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 : ANOutput
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 3Sample Output 1
21When 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 9Sample Output 2
25Sample Input 3
3 5 5 1Sample 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;
}
说点什么