国际交流会

排序后双指针交替输出即可

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        vector<int> people(n);
        for(int i = 0; i < n; i++){
            cin >> people[i];
        }
        sort(people.begin(), people.end());
        vector<int> ans;
        int i = 0, j = n - 1;
        while(i <= j){
            if(i <= j) ans.push_back(people[i++]);
            if(i <= j) ans.push_back(people[j--]);
        }
        long sum = abs(ans[0] - ans[n - 1]);
        for(int i = 1; i < n; i++){
            sum += abs(ans[i] - ans[i - 1]);
        }
        cout << sum << endl;
        for(int i = 0; i < n; i++){
            cout << ans[i] << " ";
        }
        cout << endl;
    }
}

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] features = new long[n];
        for(int i = 0; i < n; i++){
            features[i] = sc.nextLong();
        }
        
        // 从小到大排序
        Arrays.sort(features);
        
        // 从中间和最左边开始取，这样每次取的之间距离是相同的
        // 这样特征值相差最平均
        int mid = n / 2, i = 0;
        int j = mid;
        ArrayList<Long> seats = new ArrayList(n);
        long res = 0;
        while(i < mid && j < n){
            seats.add(features[j]);
            seats.add(features[i]);
            i++;
            j++;
        }
        if(j < n){
            seats.add(features[j]);
        }
        //计算差值和
        for(i = 1; i < n; i++){
            res += Math.abs(seats.get(i) - seats.get(i - 1));
        }
        res += Math.abs(seats.get(0) - seats.get(seats.size() - 1));
        System.out.println(res);
        for(Long s : seats){
            System.out.print(s + " ");
        }
    }
}

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
tmp = []
if n % 2 == 0:
    p2 = n // 2
else:
    p2 = n // 2 + 1
p1 = 0
index = p2
while p1 < index and p2 < n:
    tmp.append(arr[p1])
    p1 += 1
    tmp.append(arr[p2])
    p2 += 1
if p1 < index:
    tmp.append(arr[p1])
ans = 0
for i in range(n - 1):
    ans += abs(tmp[i] - tmp[i + 1])
ans += abs(tmp[0] - tmp[n - 1])
print(ans)
for i in tmp:
    print(i, end=" ")

若排序后的序列为b, 则差异和为

如果将绝对值符号拆出来, 每个数会被运算两次, 有三种情况: 两次加, 一次加一次减, 两次减

其中加和减的数量一致, 当且仅当n为奇数时会出现一个数进行一次加一次减

所以我们希望两次加的情况尽可能给大的数, 两次减的情况给尽可能小的数, 此时就是最优解

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
signed main() {
    int n; cin >> n;
    vector<int> a(n);
    for(int &t : a) cin >> t;
    sort(a.begin(), a.end());
    vector<int> b(n);
    for(int l = 0, r = n-1, i = 0; i < n; ++ i )
        if(i & 1) b[i] = a[l++];
        else b[i] = a[r--];
    int ans = 0;
    for(int i = 0; i < n; ++ i) 
        ans += abs(b[i] - b[(i+1)%n]);
    cout << ans << endl;
    for(int t : b) cout << t << " ";
    cout << endl;
}

#include<iostream>
#include<algorithm>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll Abs(ll a,ll b)
{
    if(a>=b) return a-b;
    else return b-a;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int n,p1,p2,index;
    ll ans=0;
    cin>>n;
    ll a[n];
    vector<ll> tmp;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n); //smaller--->larger
    if(n%2==0) p2=n/2;
    else p2=n/2+1;
    p1=0;
    index=p2;
    while(p1<index && p2<n)
    {
        tmp.push_back(a[p1]);
        p1+=1;
        tmp.push_back(a[p2]);
        p2+=1;
    }
    if(p1<index) tmp.push_back(a[p1]);
    for(int i=0;i<n-1;i++) 
    {
        ans+=Abs(tmp[i],tmp[i+1]);
    }
    ans+=Abs(tmp[0],tmp[n-1]);
    cout<<ans<<endl;
    for(int i:tmp) 
    {
        cout<<i<<" ";
    }
    cout<<endl;
    return 0;
}

个数分奇数和偶数，然后将其排序，大的存为L1，小的存为L2,然后将其逐个添加到新列表中，在计算，但是不晓得为什么就只有40的通过率，也没有反例


while True:
    try:
        a=int(input())
        L=list(map(int ,input().split()))
        L.sort()
        d=[]
        res=0

        if a%2==0:
            L1=L[:len(L)//2]
            L2=L[len(L)//2:]
            L1.sort(reverse=True)
            for i in range(a//2):
                d.append(L1[i])
                d.append(L2[i])
            for i in range(a):
                res+=abs(d[i]-d[i-1])
        else:
            L1=L[:len(L)//2]
            L1.sort(reverse=True)
            L2=L[len(L)//2+1:]
            for i in range(a//2):
                d.append(L2[i])
                d.append(L1[i])
            d.append(L2[-1])
            for i in range(a):
                res+=abs(d[i]-d[i-1])
        print(res)
        print(' '.join(map(str,d)))

    except:
        break