Skip to content

「HAOI2006」均分数据

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

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

σ=1ni=1n(xxi)2,x=1ni=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,62,52,53,43,4 分别为一组.

#数据范围与提示

  • 对于 40%40\% 的数据,保证有 mn10m \le n \le 102m62 \le m \le 6
  • 对于 100%100\% 的数据,保证有 mn20m \le n \le 202m62 \le m \le 6

#思路

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

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

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

#代码

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