Skip to content

「HAOI2006」均分数据

题解686 字
# 洛谷 # BZOJ # 2006 # STL # HAOI # 随机化
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

已知 nn 个正整数 a1,a2...ana_1,a_2 ... a_n 。今要将它们分成 mm 组，使得各组数据的数值和最平均，即各组的均方差最小。均方差公式如下：

σ=1n∑i=1n(x‾−xi)2,x‾=1n∑i=1nxi\sigma = \sqrt{\frac 1n \sum\limits_{i=1}^n(\overline x - x_i)^2},\overline x = \frac 1n \sum\limits_{i=1}^n x_i

其中 σ\sigma 为均方差，xˉ\bar{x} 为各组数据和的平均值，xix_i 为第 ii 组数据的数值和。

#输入格式

第一行是两个整数，表示 n,mn,m 的值（nn 是整数个数，mm 是要分成的组数）

第二行有 nn 个整数，表示 a1,a2...ana_1,a_2 ... a_n。整数的范围是 [1,50][1, 50]。

#输出格式

输出一行一个实数，表示最小均方差的值(保留小数点后两位数字)。

#输入输出样例

样例输入 #1

6 3
1 2 3 4 5 6

样例输出 #1

0.00

样例解释 #1

1,61,6、2,52,5、3,43,4 分别为一组.

#数据范围与提示

  • 对于 40%40\% 的数据，保证有 m≤n≤10m \le n \le 10，2≤m≤62 \le m \le 6；
  • 对于 100%100\% 的数据，保证有 m≤n≤20m \le n \le 20，2≤m≤62 \le m \le 6。

#思路

一个乱搞的贪心做法：对于每个 aia_i 都将其插入到组内值总和最小的组中，这样可以使得方差尽可能小。

但看起来这样搞出来的答案正确性不太行，所以需要将 aa 数组进行全排列来找出正确答案，然后复杂度就达到了 O(n!)O(n!) 的级别，显然跑不过这道题。

那么可以试试使用 std::shuffle 函数来碰碰运气，多打乱几次，找到最优解的概率就大大增加了。

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <numeric>
#include <random>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    double ans = 1e9;
    std::mt19937 rng(std::random_device{}());

    cin >> n >> m;

    std::vector<int> a(n);

    for (int& x : a) cin >> x;

    for (int i = 0; i < 1000000; i++) {
        std::vector<int> b(m);

        std::shuffle(a.begin(), a.end(), rng);

        for (int x : a) {
            *std::min_element(b.begin(), b.end()) += x;
        }

        double avg = static_cast<double>(std::accumulate(b.begin(), b.end(), 0)) / m;
        double variance = std::sqrt(std::accumulate(b.begin(), b.end(), 0.0, [&](double sum, int x) { return sum + std::pow(avg - static_cast<double>(x), 2); }) / m);

        ans = std::min(ans, variance);
    }

    cout << std::fixed << std::setprecision(2) << ans << endl;

    return 0;
}