ArabellaCPC 2019 I:Bashar and Hamada 贪心

Bashar and Hamada

给你一个长度为 n 的数组

选k个数，使F=，ai 、aj  k个数，i！= j 。求k=2，3，……n时，F的最大值

1. 首先n=2时，肯定选择数组中的最大值和最小值，这样F2=max-min，F2最大
2. n=3时，在F2的，然后无论选择哪个，假设选取的数是x，F3=F2 + max - x + x - min = 2 * F2                                                     
3. n=4时，在F3的基础上，随便取一个数 y， F4 =F3 + max - y + y - min +| y - x | = F3 + F2 + | y - x | ,要想使F4最大，x、y需要分别为剩下数中最小值和最大值。                                                                                                                                                     

排序，每次取最小或者最大，一定是最优的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+100;
int n;
ll a[N];
ll d[N];
ll sum[N];
ll suf[N];
int main(){
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i] ;
	}
	sort( a+1, a+1+n);
	suf[n+1] = 0;
	sum[0] = 0;
	for(int i = n ; i >= 0; i --){
		suf[i] = suf[i+1] + a[i];
		sum[n-i+1] = sum[n-i] + a[n-i+1];
	}
	int l = 2, r = n - 1;
	d[2] = a[n] - a[1];
	for(int i = 3; i <= n ; i ++){
		if(i % 2){
			d[i] = d[i-1] + (l-1)*a[l] - sum[l-1] + suf[r+1] - (n-r)*a[l];
            //d[i] = d[i-1] + 新插入的数与前面数差的绝对值 + 新插入的数与后面数差的绝对值
			l++;
		}
		else{
			d[i] = d[i-1] + (l-1)*a[r] - sum[l-1] + suf[r+1] - (n-r)*a[r];
			r--;
		}
	}
	for(int i = 2; i <= n; i++){
		cout << d[i] << (i==n ? "\n":" ");
	}
	return 0;
}