题解：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\}

，发现每一组的中位数是在左边取的最后一个数字，规律就是这么来的。

所以，代码就产生了：

CPP

#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;
}

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

题解：P13759 Basketball

文章操作

相关推荐

评论

题解：P13759 Basketball