题解：P13759 Basketball

· · 题解

题解：P13759 Basketball

题目传送门

观察到题目并没有样例解释，并且我们的第六感告诉我们这是一道结论题，于是，我们使用 dfs 来解释样例（请读者自行实现 dfs 代码）。

最终得到的解释如下：

1 2 7
3 4 8
5 6 9

答案为 2+4+6=12。

前面说了，这是一道结论题。于是，我们手玩数据造几个数据，发现：设 k = \frac{n}{m}，然后把 a 排序，答案为 \sum_{i=1}^{m} a_{i \times \frac{k+1}{2}}。

那么，代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[1000005],l,ans;
signed main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+n+1);
    int k = n / m;
    l = 0;
    for (int i = 1; i <= m; i++){
        l += (k + 1) / 2;
        ans += a[l];
    }
    cout << ans;
    return 0;
}

时间复杂度 O(n \log n)，跑得飞快。