OPPO手机DIY大赛评分

[题目链接](https://www.nowcoder.com/practice/e4a33743de5f4d82905d3b56a652858f)

思路

n 位评委分别为外观和性能两个维度打分。对于每个维度，去掉最高分和最低分后取平均，最终得分是两个维度平均分的均值。现在要求：如果第 i 位评委失去资格（被移除），最终得分是多少。

核心观察

对每个维度独立处理。设该维度所有分数之和为 $S$ ，将分数排序后得到 $v_0 \leq v_1 \leq \cdots \leq v_{n-1}$ 。

当移除评委 $i$ （其在排序数组中的位置为 $p$ ）后，剩余 $n-1$ 个分数需要再去掉最高和最低：

新最小值：若 $p = 0$ （即移除的恰好是最小值位置），新最小值为 $v_1$ ；否则仍为 $v_0$ 。
新最大值：若 $p = n-1$ （即移除的恰好是最大值位置），新最大值为 $v_{n-2}$ ；否则仍为 $v_{n-1}$ 。
中间部分之和： $S - v_p - \text{新最小值} - \text{新最大值}$ 。
该维度平均分：中间部分之和 $/ (n-3)$ 。

最终得分 = 两个维度平均分之和 $/ 2$ 。

为什么这样是对的

排序后，位置 $0$ 是唯一可能影响最小值的位置，位置 $n-1$ 是唯一可能影响最大值的位置。移除中间位置的评委不会改变剩余序列的最小值和最大值。

时间复杂度

排序 $O(n \log n)$ ，每个评委的计算 $O(1)$ ，总复杂度 $O(n \log n)$ 。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) cin >> a[i] >> b[i];

    auto solve = [&](vector<int>& arr) -> vector<double> {
        vector<int> idx(n);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int a, int b){ return arr[a] < arr[b]; });
        vector<int> pos(n);
        for(int i = 0; i < n; i++) pos[idx[i]] = i;
        vector<int> sv(n);
        for(int i = 0; i < n; i++) sv[i] = arr[idx[i]];
        long long S = 0;
        for(int x : arr) S += x;
        vector<double> res(n);
        for(int i = 0; i < n; i++){
            int p = pos[i];
            int mn = (p == 0) ? sv[1] : sv[0];
            int mx = (p == n-1) ? sv[n-2] : sv[n-1];
            res[i] = (double)(S - arr[i] - mn - mx) / (n - 3);
        }
        return res;
    };

    auto ra = solve(a), rb = solve(b);
    cout << fixed << setprecision(12);
    for(int i = 0; i < n; i++)
        cout << (ra[i] + rb[i]) / 2.0 << "\n";
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        int[] a = new int[n], b = new int[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            a[i] = Integer.parseInt(st.nextToken());
            b[i] = Integer.parseInt(st.nextToken());
        }
        double[] ra = solve(a, n), rb = solve(b, n);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++)
            sb.append(String.format("%.12f%n", (ra[i] + rb[i]) / 2.0));
        System.out.print(sb);
    }

    static double[] solve(int[] arr, int n) {
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (x, y) -> arr[x] - arr[y]);
        int[] pos = new int[n], sv = new int[n];
        for (int i = 0; i < n; i++) { pos[idx[i]] = i; sv[i] = arr[idx[i]]; }
        long S = 0;
        for (int v : arr) S += v;
        double[] res = new double[n];
        for (int i = 0; i < n; i++) {
            int p = pos[i];
            int mn = (p == 0) ? sv[1] : sv[0];
            int mx = (p == n - 1) ? sv[n - 2] : sv[n - 1];
            res[i] = (double)(S - arr[i] - mn - mx) / (n - 3);
        }
        return res;
    }
}

import sys
input = sys.stdin.readline

def solve(arr, n):
    idx = sorted(range(n), key=lambda i: arr[i])
    pos = [0] * n
    for i, j in enumerate(idx):
        pos[j] = i
    sv = [arr[idx[i]] for i in range(n)]
    S = sum(arr)
    res = [0.0] * n
    for i in range(n):
        p = pos[i]
        mn = sv[1] if p == 0 else sv[0]
        mx = sv[n-2] if p == n-1 else sv[n-1]
        res[i] = (S - arr[i] - mn - mx) / (n - 3)
    return res

n = int(input())
a, b = [0]*n, [0]*n
for i in range(n):
    x, y = map(int, input().split())
    a[i], b[i] = x, y

ra, rb = solve(a, n), solve(b, n)
print('\n'.join(f"{(ra[i]+rb[i])/2:.12f}" for i in range(n)))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = new Array(n), b = new Array(n);
    for (let i = 0; i < n; i++) {
        const p = lines[i+1].split(/\s+/);
        a[i] = parseInt(p[0]); b[i] = parseInt(p[1]);
    }
    function solve(arr) {
        const idx = Array.from({length:n},(_,i)=>i);
        idx.sort((x,y) => arr[x]-arr[y]);
        const pos = new Array(n), sv = idx.map(i=>arr[i]);
        for (let i=0;i<n;i++) pos[idx[i]]=i;
        let S = 0;
        for (let v of arr) S += v;
        const res = new Array(n);
        for (let i=0;i<n;i++) {
            const p = pos[i];
            const mn = p===0 ? sv[1] : sv[0];
            const mx = p===n-1 ? sv[n-2] : sv[n-1];
            res[i] = (S - arr[i] - mn - mx) / (n-3);
        }
        return res;
    }
    const ra = solve(a), rb = solve(b);
    const out = [];
    for (let i=0;i<n;i++) out.push(((ra[i]+rb[i])/2).toFixed(12));
    console.log(out.join('\n'));
});