解题思路

• 核心转化：固定窗口大小为 m，最终成绩为 (sum - min - max) / (m - 2)。因为分母固定，最大化平均值等价于最大化分子 sum - min - max。

• 滑动窗口：

  • 维护窗口和 wsum（进入加、移出减）。

  • 维护窗口最小值与最大值：用两个单调队列

    • 递增队列维护最小值（队头最小）
    • 递减队列维护最大值（队头最大）

  • 每次窗口形成（i >= m-1）时，取

    • mn = a[inc.front()]
    • mx = a[dec.front()]
    • 当前得分和 val = wsum - mn - mx

  • 记录最大 val 的窗口起点；若相等取起点更小者。

• 正确性：分母固定，最大化分子即可；单调队列在均摊 O(1) 时间维护窗口极值；并且当所有元素相等时，min==max 也没问题，等价于删去两个相同值。

复杂度分析

• 时间复杂度：O(n)，每个元素进出各单调队列至多一次。
• 空间复杂度：O(m)（队列存索引），数组 O(n)。

Python 代码

import sys
from collections import deque

def main():
    data = sys.stdin.read().strip().split()
    n, m = map(int, data[:2])
    a = list(map(int, data[2:]))

    inc = deque()  # 维护最小值（递增）
    dec = deque()  # 维护最大值（递减）
    wsum = 0
    best_val = None
    best_l = 0

    for i, x in enumerate(a):
        wsum += x
        # 维护递增队列（最小值）
        while inc and a[inc[-1]] >= x:
            inc.pop()
        inc.append(i)
        # 维护递减队列（最大值）
        while dec and a[dec[-1]] <= x:
            dec.pop()
        dec.append(i)

        # 窗口左端
        if i >= m:
            # 移出 i-m 位置
            wsum -= a[i - m]
        # 弹出过期索引
        while inc and inc[0] <= i - m:
            inc.popleft()
        while dec and dec[0] <= i - m:
            dec.popleft()

        if i >= m - 1:
            mn = a[inc[0]]
            mx = a[dec[0]]
            val = wsum - mn - mx
            l = i - m + 1
            if best_val is None or val > best_val or (val == best_val and l < best_l):
                best_val = val
                best_l = l

    print(best_l + 1)

if __name__ == "__main__":
    main()

Java 代码

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		long[] a = new long[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken());

		Deque<Integer> inc = new ArrayDeque<>(); // 递增，取最小
		Deque<Integer> dec = new ArrayDeque<>(); // 递减，取最大
		long wsum = 0;
		long bestVal = Long.MIN_VALUE;
		int bestL = 0;
		boolean inited = false;

		for (int i = 0; i < n; i++) {
			long x = a[i];
			wsum += x;

			while (!inc.isEmpty() && a[inc.peekLast()] >= x) inc.pollLast();
			inc.addLast(i);
			while (!dec.isEmpty() && a[dec.peekLast()] <= x) dec.pollLast();
			dec.addLast(i);

			if (i >= m) {
				wsum -= a[i - m];
			}
			while (!inc.isEmpty() && inc.peekFirst() <= i - m) inc.pollFirst();
			while (!dec.isEmpty() && dec.peekFirst() <= i - m) dec.pollFirst();

			if (i >= m - 1) {
				long mn = a[inc.peekFirst()];
				long mx = a[dec.peekFirst()];
				long val = wsum - mn - mx;
				int l = i - m + 1;
				if (!inited || val > bestVal || (val == bestVal && l < bestL)) {
					bestVal = val;
					bestL = l;
					inited = true;
				}
			}
		}
		System.out.println(bestL + 1);
	}
}

C++ 代码

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	if (!(cin >> n >> m)) return 0;
	vector<long long> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];

	deque<int> inc, dec; // inc维护最小，dec维护最大
	long long wsum = 0;
	long long bestVal = LLONG_MIN;
	int bestL = 0;
	bool inited = false;

	for (int i = 0; i < n; ++i) {
		long long x = a[i];
		wsum += x;

		while (!inc.empty() && a[inc.back()] >= x) inc.pop_back();
		inc.push_back(i);
		while (!dec.empty() && a[dec.back()] <= x) dec.pop_back();
		dec.push_back(i);

		if (i >= m) {
			wsum -= a[i - m];
		}
		while (!inc.empty() && inc.front() <= i - m) inc.pop_front();
		while (!dec.empty() && dec.front() <= i - m) dec.pop_front();

		if (i >= m - 1) {
			long long mn = a[inc.front()];
			long long mx = a[dec.front()];
			long long val = wsum - mn - mx;
			int l = i - m + 1;
			if (!inited || val > bestVal || (val == bestVal && l < bestL)) {
				bestVal = val;
				bestL = l;
				inited = true;
			}
		}
	}
	cout << bestL + 1 << "\n";
	return 0;
}

• 输出即为题目所需答案。

题目内容

在一场跳水比赛中，共有 $n$ 位裁判依次为选手打分(打分均为非负整数)。根据比赛规则，需要从所有裁判的打分中，选取连续的 $m$ 个打分来计算选手的最终成绩。具体计算方式为：从这 $m$ 个打分里去掉 $1$ 个最高分和 $1$ 个最低分，最后取剩余分数的平均值作为该选手的最终成绩。

现在需要找到所有可能的连续 $m$ 个打分区间中，最终成绩最高的那个区间，并输出该区间的起始裁判编号(从 $1$ 开始计数)。如果有多个区间的最终成绩相同，输出起始编号最小的那个。

输入描述

第一行包含两个正整数 $n$ 和 $m(3≤m≤n≤10^5)$ 分别表示裁判总数和选取的连续打分个数。

第二行包含 $n$ 个非负整数 $a_1,a_2,...,a_n(0≤a_i≤10^9)$，表示每位裁判的打分。

输出描述

输出一个正整数，表示最终成绩最高的区间的起始裁判编号。

样例1

输入

6 4
4 2 8 5 9 3

输出

2

样例2

输入

5 3
4 3 4 4 4

输出

1