题解：CF1175C Electrification

Wang_H_Y · 2025-01-14 10:14:33 · 题解

CF1175C 电气化

题目传送门

本人的第一篇题解 。

题目大意

有 n 个数 a_n ，寻找一个数 x ，使得第 k+1 小的 \left | a_i-x \right | 最小。

思路

根据 小学二年级的 知识我们知道， \left | a_i-x \right | 代表着 a_i 到 x 的距离，题目就变成了寻找离 x 最近的第 k+1 个点。

枚举每一个数作为第 k+1 小的数所产生的答案，如同其它大佬们的题解一样，对于任意的一个 x ，离 x 最近的 k+1 个点一定对应原来的 a 的一段区间。而第 k+1 远的一定是这个区间的左端点或者右端点。

这里我枚举的是左端点，那么离 x 最近的 k+1 个点就是 a_{i-k},a_{i-k+1},…,a_i ，为了 a_i 和 a_{i-k} 离 x 更近，我们要把 x 放在中间，也就是左端点+区间长度的一半。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int t,n,k;
int a[N];
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i];
        int mi=INT_MAX,ans=0;
        for(int i=1;i<=n-k;i++)//枚举左端点
        {
            if(mi>a[i+k]-a[i])
            {
                mi=a[i+k]-a[i];//更新区间长度
                ans=a[i]+mi/2;//位置在现在区间的中点，也就是左端点+区间长度的一半
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}

谢谢观看