疯狂队列

#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n, 0);
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	sort(a.begin(), a.end());
	int i = 0;
	int j = n - 1;
	int ret = abs(a[0] - a[n - 1]);
	while (i <= n / 2 - 2)
		ret += abs(a[i] - a[j - 1]) + abs(a[(i++) + 1] - a[(j--)]);
	if (n % 2 == 1)
        ret += max(abs(a[(n-1)/2-1]-a[(n-1)/2]),abs(a[(n-1)/2+1]-a[(n-1)/2]));
	cout << ret << endl;
	return 0;
}

n = int(input())
l = list(map(int,input().split()))

l.sort()
temp =[l[0]]
left = 1
right = n-1
res = 0
while left<=right:
    r0 = abs(temp[0] - l[right])
    lr = abs(temp[-1] - l[right])
    l0 = abs(temp[0]-l[left])
    l1 = abs(temp[-1]-l[left])
    tl = [r0,lr,l0,l1]
    m = max(tl)
    if tl.index(m)==0:
        temp.insert(0,l[right])
        right-=1
    if tl.index(m)==1:
        temp.append(l[right])
        right-=1
    if tl.index(m)==2:
        temp.insert(0,l[left])
        left+=1
    if tl.index(m)==3:
        temp.append(l[left])
        left+=1


for i in range(n-1):
    res+=abs(temp[i+1]-temp[i])
print(res) 

//又是找规律，例子中两个25感觉就是个坑，就是先放入大的，大的两边放小的，然后在次大的，然后......
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;

void Judge(deque<int> &arr,deque<int> &result, int i)
{
	if(i%2 == 0)
	{
		result.push_back(arr[0]);
		arr.pop_front();
		//这里如果不加判断，则如1 1 1 1 1 1 1 500 500 500 500 1000 1000 1000 1000就会出错，因为按照顺序来就错啦，所以最后一个需要进行判断；
		if(arr.size() == 1 && (abs(arr[0] - result[0]) < abs(result[result.size() - 1] - arr[0])))
		{
			result.push_back(arr[0]);
		}
		else
			result.push_front(arr[0]);
		arr.pop_front();
	}
	else
	{
		result.push_back(arr[arr.size() - 1]);
		arr.pop_back();
		if(arr.size() == 1 && (abs(arr[0] - result[0]) < abs(result[result.size() - 1] - arr[0])))
		{
			result.push_back(arr[0]);
		}
		else
			result.push_front(arr[arr.size() - 1]);
		arr.pop_back();
	}
}

int main()
{
	deque<int> arr, result;
	int sum = 0;
	int count = 0;
	int input;
	int n;
	cin>>n;
	while(cin>>input)
	{
		arr.push_back(input);
	}
	sort(arr.begin(), arr.end());
	result.push_back(arr[n - 1]);
	arr.pop_back();
	if(n % 2 == 0)
	{
		for(int i = 0; i < (n - 2)/2; i++)
		{
			Judge(arr, result, i);
		}
		result.push_back(arr[0]);
	}
	else
	{
		for(int i = 0; i < (n - 1)/2; i++)
		{
			Judge(arr, result, i);
		}
	}
	for(int i = 1; i < n; i++)
	{
		count = result[i] - result[i - 1]; 
		sum = sum + abs(count);
	}
	cout << sum << endl;
	return 0;
}

占用内存：3568k

""""
思路:先将height排序，每一次取出最小值和最大值放在队列中
     然后再取出最小值和最大值,最小值放在上次最大值的右边
     最大值放在上次最小值的左边
     Note：需要判断输入个数的奇偶性，若是奇数，最后一个元素
     是防止在队头或者队尾，需要和当前的队头和队尾元素比较
eg1: 25-10-40-5-25(n为奇数)
    sort:5-10-25-25-40
    第一次取出min=5,max=40  queue:[5,40]
    第二次取出min=10,max=25 queue:[25,5,40,10]
    第三次取出25,放在队头or队尾？明显放在队尾差异更大 queue:[25,5,40,10,25]
    res = 20+35+30+15=100
eg2：1-2-4-8-6-10(n为偶数)
    sort:1-2-4-6-8-10
    第一次取出min=1,max=10 queue:[1,10]
    第一次取出min=2,max=8 queue:[8,1,10,2]
    第一次取出min=4,max=6 queue:[4,8,1,10,2,6]
    res = 4+7+9+8+4=32
    
"""
n = int(input())
height = list(map(int,input().split()))
height.sort()
min_value = height[0]
max_value = height[-1]
res = abs(max_value-min_value)
# 队头指针
top = 1
# 队尾指针
rear = n-2
while top<=rear:
    # 当n为奇数时，最后一步top==rear
    if top==rear:
        res += max(abs(min_value-height[top]),abs(max_value-height[rear]))
    else:
        # 计算右边差距
        res += abs(max_value-height[top])
        # 计算左边差距
        res += abs(min_value-height[rear])
        # update min and max
        min_value = height[top]
        max_value = height[rear]
    # 移动指针
    top += 1
    rear -=1
print(res)

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int> a;
    for (int i=0;i<n;i++){
        int temp;
        cin>>temp;
        a.push_back(temp);
    }
    sort(a.begin(),a.end());
    deque<int> b;
    int i=0;
    int j=n-1;
    int cnt=0;
    while(i<j){
        if (cnt%2==0 && i<j)
        {
    		b.push_back(a[j--]);
    		b.push_front(a[i++]);}
        else if (cnt%2==1 && i<j)
        {
    		b.push_back(a[i++]);
    		b.push_front(a[j--]);
        }
        cnt++;
    }
    if(i==j)//如果i=j，就是有奇数个的情况
    {
        if(abs(a[i]-b[0])>abs(a[i]-b[n-2])){
            b.push_front(a[i]);}
        else{
            b.push_back(a[i]);}
    }
    int res=0;
    for (int i=1;i<b.size();i++){
        res+=abs(b[i]-b[i-1]);
    }
    cout<<res<<endl;
    return 0;
}

//AC代码：
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
using namespace std;
int main(){
    int N,i,a[100];
    //freopen("input.txt","r",stdin);
    while(scanf("%d",&N)!=EOF){
        for(i=0;i<N;i++) scanf("%d",&a[i]);
        vector<int> d(N);
        sort(a,a+N);
        deque<int> Q;
        Q.push_back(a[N-1]);
        int l=0,r=N-2,flag=1;
        while(l<r){
            int cnt=1,a1,a2;
            if(flag==1){
                a1=a[l++];
                if(l<r) a2=a[l++],cnt++;
            }else{
                a1=a[r--];
                if(l<r) a2=a[r--],cnt++;
            }
            if(cnt==1)
                abs(Q.front()-a1)<abs(Q.back()-a1)?Q.push_back(a1):Q.push_front(a1);
            else{
                if(abs(Q.front()-a1)+abs(Q.back()-a2)<abs(Q.front()-a2)+abs(Q.back()-a1)){
                    Q.push_front(a2);
                    Q.push_back(a1);
                }else{
                    Q.push_front(a1);
                    Q.push_back(a2);
                }
            }
            flag=!flag;
        }
        if(l==r) abs(Q.front()-a[l])<abs(Q.back()-a[l])?Q.push_back(a[l]):Q.push_front(a[l]);
        int pre=Q.front(),res=0; Q.pop_front();
        while(!Q.empty()){
            res+=abs(Q.front()-pre);
            pre=Q.front();
            Q.pop_front();
        }
        printf("%d\n",res);
    }
}//双端队列，前插后插，乱搞，过了

//血的教训，就算调不出来最后那个bug，也至少得90%，然而考试只过了20%，boom!
//总体思路：先放最大的数，然后两边放最小的数，再两边放次大和次次大的数，
//再两边放小的数...直到放完，最后要检查一下两边的元素位置是否合适,不合适的话移动一下
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
 
int main()
{
    int n;
    while(cin>>n)
    {
        vector<int> a(n);
        for(int i=0;i<n;++i)
            cin>>a[i];
        if(1==n)
        {
            cout<<a[0]<<endl;
            return 0;
        }
 
        sort(a.begin(),a.end());
 
        vector<int> b;
        //b.reserve(n);
 
        b.push_back(a[n-1]);
 
        int left=-1;
        int right=n-1;
 
        int flag=1;
        while(left+1<right)
        {
            if(flag)
            {
                b.insert(b.begin(),a[++left]);
                if(left<right)
                    b.push_back(a[++left]);
            }
            else
            {
                b.insert(b.begin(),a[--right]);
                if(left<right)
                    b.push_back(a[--right]);
            }
            flag^=1;
        }
        //这段代码是检测最后一个元素的放置的位置是否合适，不合适的话移到最前面
        //如果没有这一步检查，只能过90%
        if(abs(b[n-1]-b[n-2])<abs(b[n-1]-b[0]))
        {
            int tmp=b[n-1];
            b.erase(b.end()-1);
            b.insert(b.begin(),tmp);
        }
 
        int h=0;
        for(int i=1;i<n;++i)
        {
            h+=abs(b[i]-b[i-1]);
        }
        cout<<h<<endl;
    }
 
    return 0;
}

逆向排序，分成较大部分和较小部分。再分奇偶讨论即可。

import math
def solve(nums):
    if len(nums) == 1: return nums[0]
    nums = sorted(nums, reverse=True)
    length = len(nums)
    max_part = nums[0: math.ceil(length / 2)]
    min_part = nums[math.ceil(length / 2):]
    if len(nums) % 2 == 0:
        return 2 * sum(max_part[:-1]) + max_part[-1] - 2 * sum(min_part[1:]) - min_part[0]
    else:
        return 2 * sum(max_part[:-2]) + max_part[-2] + max_part[-1] - 2 * sum(min_part)

while True:
    try:
        n=int(input())
        h=sorted(list(map(int,input().split())))
        Max,Min,res=0,0,0
        if n%2==1:
            while(len(h)>1):
                res+=h[-1]-Min+Max-h[0]
                Min=h.pop(0)
                Max=h.pop(-1)
            res+=max(abs(h[0]-Min),abs(h[0]-Max))
            print(res)
        else:
            while(len(h)>0):
                res+=h[-1]-Min+Max-h[0]
                Min=h.pop(0)
                Max=h.pop(-1)
            print(res)
    except:
        break

# 先写出一部分在进行公式推导，可分为长度为偶数和奇数的情况，奇数又可以分为ABAB和BABA的情况
def crazy(n: int, h: [int]) -> int:
    if n == 1:
        return 0
    else:
        h = sorted(h)
        if n%2 == 0:
            return 2*sum(h[n//2+1:]) + h[n//2] - 2*sum(h[:n//2-1]) -h[n//2-1]  # 人数为偶数
        else:
            t1 = 2*sum(h[n//2+1:]) - 2*sum(h[:n//2-1]) - sum(h[n//2-1:n//2+1])  # 人数为奇数，且较小的数在较大的数后面
            t2 = 2*sum(h[n//2+2:]) + sum(h[n//2:n//2+2]) - 2*sum(h[:n//2])   # 人数为奇数，且较大的数在较小的数后面
            return max(t1, t2)

if __name__ == "__main__":
    n = int(input())
    h = list(map(int, input().split()))
    print(crazy(n, h))

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

int main(){
    int n;
    scanf("%d", &n);
    int a[n];
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);
    sort(a, a+n);
    int Max=a[n-1], Min=a[0], l=1, r=n-2, s=Max-Min;
    while(l<r){
        s += (Max-a[l]) + (a[r]-Min);
        Min = a[l++];
        Max = a[r--];
    }
    s += max(Max-a[l], a[r]-Min);
    printf("%d\n", s);
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int a[55], mark[55];

deque<int> d;

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a, a + n);
  d.push_back(a[n - 1]);
  mark[n - 1] = 1;
  int total = n - 1;
  while(total) {
    int Max = 0, idx = 0;
    for (int i = 0; i < n; i++) {
      if (!mark[i]) {
        int tmp = max(abs(a[i] - d.front()), abs(a[i] - d.back()));
        if (tmp > Max) {
          idx = i;
          Max = tmp;
        }
      }
    }
    mark[idx] = 1;
    total--;
    if (abs(a[idx] - d.front()) > abs(a[idx] - d.back())) {
      d.push_front(a[idx]);
    } else {
      d.push_back(a[idx]);
    }
  }
  int ans = 0;
  for (int i = 1; i < (int)d.size(); i++) {
    ans += abs(d.at(i) - d.at(i - 1));
  }
  cout << ans << "\n";
  return 0;
}

while True:
    try:
        n = int(input())
    except:
        break
    h = list(map(int, input().split()))
    h.sort()
    if len(h) < 2:
        print(0)
        continue
    q = [h.pop()]
    flag = 0
    while len(h) > 2:
        if flag == 0:
            h1 = h.pop(0)
            h2 = h.pop(0)
            flag = 1
        else:
            h1 = h.pop()
            h2 = h.pop()
            flag = 0
        if abs(h1 - q[0]) + abs(h2 - q[-1]) > abs(h1 - q[-1]) + abs(h2 - q[0]):
            q.insert(0, h1)
            q.append(h2)
        else:
            q.insert(0, h2)
            q.append(h1)
    if len(h) == 1:
        h1 = h.pop()
        if abs(h1 - q[0]) > abs(h1 - q[-1]):
            q.insert(0, h1)
        else:
            q.append(h1)
    elif len(h) == 2:
        h1 = h.pop()
        h2 = h.pop()
        case1 = abs(h1 - q[0])
        case2 = abs(h1 - q[-1])
        case3 = abs(h2 - q[0])
        case4 = abs(h2 - q[-1])
        case = max(case1, case2, case3, case4)
        if case == case1 or case == case2:
            if case == case1:
                q.insert(0, h1)
            elif case == case2:
                q.append(h1)
            if abs(h2 - q[0]) > abs(h2 - q[-1]):
                q.insert(0, h2)
            else:
                q.append(h2)
        else:
            if case == case3:
                q.insert(0, h2)
            else:
                q.append(h2)
            if abs(h1 - q[0]) > abs(h1 - q[-1]):
                q.insert(0, h1)
            else:
                q.append(h1)
    res = 0
    for i in range(len(q) - 1):
        res += abs(q[i] - q[i+1])
    print(res)

	

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
using namespace std;
int n;
int h[51];
int main(){
    cin >> n;
    //相邻学生身高差的绝对值组合
    for(int i = 0; i < n; i++){
        cin >> h[i];
    }
    if(n == 1){
        cout << 0 << endl;
        return 0;
    }
    else if(n == 2){
        cout << abs(h[1] - h[0]) << endl;
        return 0;
    }
    //排序
    sort(h, h + n);
    int sum1 = 0;
    int sum2 = 0;
    //n为偶数 只有一种情况
    if(n % 2 == 0){
        int k = n / 2;
        sum1 = h[k];
        for(int i = k + 1; i < n; i++){
            sum1 += 2 * h[i];
        }
        for(int i = 0; i <= k - 2; i++){
            sum1 -= 2 * h[i];
        }
        sum1 -= h[k - 1];
    }
    //n为奇数 有两种情况
    else{
        int k = n / 2;
        for(int i = k + 1; i < n; i++){
            sum1 += 2 * h[i];
        }
        for(int i = 0; i <= k - 2; i++){
            sum1 -= 2 * h[i];
        }
        sum1 -= h[k];
        sum1 -= h[k - 1];
        sum2 = h[k];
        for(int i = k + 2; i < n; i++){
            sum2 += 2 * h[i];
        }
        for(int i = 0; i <= k - 1; i++){
            sum2 -= 2 * h[i];
        }
        sum2 += h[k + 1];
    }
    cout << max(sum1, sum2) << endl;
    return 0;
}

// 又是找规律分为 高低高低高，地高低高低；高低高低高低（低高低高低高）3种
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] h = new int[n];
        for(int i = 0; i < n; i++) h[i] = sc.nextInt();
        sc.close();
        int res = 0;
        Arrays.sort(h);
        if(n == 1){System.out.println(h[0]); return;}
        if((n&1) == 0){// 偶数
            int m = n>>1;
            for(int i = 0; i < m; i++) res += (h[i+m] - h[i]);
            res *= 2;
            res -= (h[m] - h[m-1]);
        }
        else{// 奇数
            // 高低高低高，中位数归高，中位数右边的那个数只加一次
            // 低高低高低，中位数归低，中位数左边的那个数只减一次
            int m = n>>1;
            for(int i = 0; i < m; i++) res += (h[i+m+1] - h[i]);
            res *= 2;
            res += h[m-1] - h[m] > h[m] - h[m+1] ? h[m-1] - h[m] : h[m] - h[m+1];
        }
        System.out.println(res);
    }
}