数列极差

题目描述

思路

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,arr[50005],save[50005];
int tmp[50005];
long long  maxx,minn;
const int inf = 0x7fffffff;
inline int read() {
    int s = 0,f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();
    return s * f;
}
int cmpa(int a,int b) {
    return a < b;
}
int cmpb(int a,int b) {
    return a > b;
}
void inserta(int * arr,int tot,int key) {
    for (int i = tot; i >= 0; --i) {
        if (arr[i] > key) arr[i + 1] = arr[i]; 
        else {
            arr[i + 1] = key;
            break;
        }
    }
}
void insertb(int * arr,int key) {
    for (int i = tot; i >= 0; --i) {
        if (arr[i] < key) arr[i + 1] = arr[i]; 
        else {
            arr[i + 1] = key;
            break;
        }
    }
}
void show(int * r,int n) {
    for (int i = 1; i <= n; ++i) {
        printf("%d ",r[i]);
    }
    puts("");
}
int main() {
    n = read();
    for (int i = 1; i <= n + 1; ++i) arr[i] = read();
    memcpy(save,arr,sizeof(arr));
    sort(arr + 1,arr + 1 + n,cmpa);
    for (int i = n; i >= 3; --i) {
        for (int j = 1; j <= i - 2; ++j) tmp[j] = arr[j + 2];
        inserta(tmp,i - 2,arr[1] * arr[2] + 1);
        for (int j = 1; j <= i - 1; ++j) arr[j] = tmp[j];  
    }
    maxx = arr[1] * arr[2] + 1;
    memcpy(arr,save,arr + n + 1,cmpb);
    for (int i = n; i >= 3; --i) {
        for (int j = 1; j <= i - 2; ++j) tmp[j] = arr[j + 2];
        tmp[0] = inf;
        insertb(tmp,arr[1] * arr[2] + 1);
        for (int j = 1; j <= i - 1; ++j) arr[j] = tmp[j];
    }
    minn = arr[1] * arr[2] + 1;
    printf("%lldn",maxx - minn);
    return 0;
}