题面描述

给定一个数组 $X$ 和正整数 $K$，请找出使表达式：

结果最接近于数组中位数的下标 $i$。如果有多个 $i$ 满足条件，请返回最大的 $i$。

数组中位数的定义为：对于长度为 $N$ 的数组，按照元素值大小升序排列后，下标为 $\lfloor N/2 \rfloor$ 的元素的值。

思路

首先，通过对数组 $X$ 进行排序来确定其中位数。然后，遍历所有可能的起始下标 $i$，计算表达式 $X[i] - X[i+1] - \dots - X[i+K-1]$ 的值，并与中位数求绝对差。过程中记录最小的差值及对应的下标，如果出现相同的最小差值，则选择较大的下标 $i$。最终返回使表达式结果最接近中位数的最大下标。

cpp

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

// 函数：查找最接近中位数的下标
int findClosestIndex(vector<int> X, int K) {
    int n = X.size();
    // 复制并排序数组以找到中位数
    vector<int> sortedX = X;
    sort(sortedX.begin(), sortedX.end());
    int median = sortedX[n / 2];
    
    int closestIndex = -1;
    long long minDiff = LLONG_MAX;
    
    // 遍历所有可能的i
    for(int i = 0; i <= n - K; ++i){
        // 计算表达式值：X[i] - X[i+1] - ... - X[i+K-1]
        long long expr = X[i];
        for(int j = 1; j < K; ++j){
            expr -= X[i + j];
        }
        // 计算与中位数的绝对差
        long long diff = abs((long long)expr - (long long)median);
        // 更新最小差值和对应的下标
        if(diff < minDiff || (diff == minDiff && i > closestIndex)){
            minDiff = diff;
            closestIndex = i;
        }
    }
    
    return closestIndex;
}

int main(){
    string input;
    // 读取整行输入
    getline(cin, input);
    
    // 查找数组部分和K的分隔位置
    size_t commaPos = input.find_last_of(',');
    
    
    // 提取数组字符串
    string arrayStr = input.substr(0, commaPos);
    // 提取K
    string KStr = input.substr(commaPos + 1);
    
    // 去除数组字符串中的方括号
    arrayStr.erase(remove(arrayStr.begin(), arrayStr.end(), '['), arrayStr.end());
    arrayStr.erase(remove(arrayStr.begin(), arrayStr.end(), ']'), arrayStr.end());
    
    // 分割数组字符串为数字
    vector<int> X;
    string num = "";
    for(char c : arrayStr){
        if(c == ','){
            if(!num.empty()){
                X.push_back(stoi(num));
                num = "";
            }
        }
        else if(isdigit(c)){
            num += c;
        }
    }
    if(!num.empty()){
        X.push_back(stoi(num));
    }
    
    // 转换K为整数
    int K = stoi(KStr);
    
    // 调用函数并输出结果
    cout << findClosestIndex(X, K) << endl;
    
    return 0;
}

python

def find_closest_index(X, K):
    n = len(X)
    # 复制并排序数组以找到中位数
    sorted_X = sorted(X)
    median = sorted_X[n // 2]

    closest_index = -1
    min_diff = float('inf')

    # 遍历所有可能的i
    for i in range(n - K + 1):
        # 计算表达式值：X[i] - X[i+1] - ... - X[i+K-1]
        expr = X[i]
        for j in range(1, K):
            expr -= X[i + j]
        # 计算与中位数的绝对差
        diff = abs(expr - median)
        # 更新最小差值和对应的下标
        if diff < min_diff or (diff == min_diff and i > closest_index):
            min_diff = diff
            closest_index = i

    return closest_index


if __name__ == "__main__":
    import sys

    # 读取整行输入
    input_line = sys.stdin.readline().strip()

    # 查找数组部分和K的分隔位置
    comma_pos = input_line.rfind(',')
   
    # 提取数组字符串
    array_str = input_line[:comma_pos]
    # 提取K
    K_str = input_line[comma_pos + 1:]

    # 去除数组字符串中的方括号
    array_str = array_str.replace('[', '').replace(']', '')

    # 分割数组字符串为数字
    X = list(map(int, array_str.split(',')))

    # 转换K为整数
    K = int(K_str)

    # 调用函数并输出结果
    print(find_closest_index(X, K))

java

import java.util.*;

public class ClosestIndexFinder {
    // 函数：查找最接近中位数的下标
    public static int findClosestIndex(int[] X, int K) {
        int n = X.length;
        // 复制并排序数组以找到中位数
        int[] sortedX = X.clone();
        Arrays.sort(sortedX);
        int median = sortedX[n / 2];
        
        int closestIndex = -1;
        long minDiff = Long.MAX_VALUE;
        
        // 遍历所有可能的i
        for(int i = 0; i <= n - K; i++){
            // 计算表达式值：X[i] - X[i+1] - ... - X[i+K-1]
            long expr = X[i];
            for(int j = 1; j < K; j++){
                expr -= X[i + j];
            }
            // 计算与中位数的绝对差
            long diff = Math.abs(expr - (long)median);
            // 更新最小差值和对应的下标
            if(diff < minDiff || (diff == minDiff && i > closestIndex)){
                minDiff = diff;
                closestIndex = i;
            }
        }
        
        return closestIndex;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 读取整行输入
        String input = sc.nextLine().trim();
        
        // 查找数组部分和K的分隔位置
        int commaPos = input.lastIndexOf(',');
        // 提取数组字符串
        String arrayStr = input.substring(0, commaPos);
        // 提取K
        String KStr = input.substring(commaPos + 1);
        
        // 去除数组字符串中的方括号
        arrayStr = arrayStr.replace("[", "").replace("]", "");
        
        // 分割数组字符串为数字
        String[] numStrs = arrayStr.split(",");
        int[] X = new int[numStrs.length];
        for(int i = 0; i < numStrs.length; i++){
            X[i] = Integer.parseInt(numStrs[i].trim());
        }
        
        // 转换K为整数
        int K = Integer.parseInt(KStr.trim());
        
        // 调用函数并输出结果
        System.out.println(findClosestIndex(X, K));
    }
}

题目描述

给定一个数组X和正整数K，请找出使表达式：

$X[i] - X[i + 1] - ... - X[i + K - 1]$

结果最接近于数组中位数的下标 $i$ ，如果有多个 $i$ 满足条件，请返回最大的 $i$.

其中，数组中位数：长度为 $N$ 的数组，按照元素的值大小升序排列后，下标为 $N/2$ 元素的值

备注

数组 $X$ 的元素均为正整数

$X$ 的长度 $n$ 取值范围：$2 ≤ n ≤ 1000$

$K$ 大于 $0$ 目小于数组的大小

$i$ 的取值范围: $0 ≤ i < 1000$

题目的排序数组 $X[N]$的中位数是 $X[N/2]$

样例1

输入

[50,50,2,3],2

输出

1

说明

中位数为 $50$ ：$[50,50,2,3]$ 升序排序后变成 $[2,3,50,50]$ ，中位数为下标 $4/2=2$ 的元素 $50$

计算结果为 $1$ ：$X [50,50,2,3]$ 根据题目计算 $X[i] - ... - X[i + k - 1]$

得出三个数 $0 (X[0] - X[1] = 50 - 50)$ 、$48 (X[1] - X[2] = 50 - 2)$ 和 $-1 (X[2]-X[3] = 2 - 3)$ ，

其中 $48$ 最接近 $50$ ，因此返回下标 $1$ 。