题解：P13759 Basketball

· · 题解

传送器~

算法：贪心

这道题其实说难不难，如果认真找规律了，基本上都能在 15 分钟内做完，甚至更短。

首先，因为是求最小，所以给它从小到大排个序。之后，我们会发现，要让 \sum_{i=1}^mx_i（x 表示中位数）最小，通过正确分组后，\sum_{i=1}^mx_i 其实就是 \sum_{i=1}^ma_{c\times i}（c 表示第一组中的下标）。

具体过程如下：

当 n=15 时，对于序列 \{1,3,4,6,5,7,9,12,10,15,20,19,18,17,16\} 且 m=3，将它排序并分成两组：\{{\color{RoyalBlue}1,3,4,5,6,7,9,10,12}\},\{{\color{Red}15,16,17,18,19,20}\}，每次从左边取 3 个（对于每一组，下标要从 1 取到中间），再从右边取 2 个，每组为 \{1,3,{\color{LimeGreen}4},15,16\},\{5,6,{\color{LimeGreen}7},17,18\},\{9,10,{\color{LimeGreen}12},19,20\}，发现每一组的中位数是在左边取的最后一个数字，规律就是这么来的。

所以，代码就产生了：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int a[N],n,m,c,ans;
signed main(){
    cin>>n>>m;
    for (int i=1; i<=n; i++){
        cin>>a[i];
    }
    sort (a+1,a+1+n);
    c=n/m/2+1; //第一组中位数的下标
    for (int i=1; i<=m; i++){
        ans+=a[c*i];
    }
    cout<<ans;
    return 0;
}

总结：本道题就是这么轻松的搞定啦！但是我们平常做题时一定要认真仔细，动脑思考，不要粗心大意，这样才有效果。