繁花题解c++/python

Question

B. 繁花
时间限制: 1000ms
空间限制: 262144kb
题目描述
Crazy 想挑选
𝑘
k 朵花作为一束收藏在书房中。于是她来到花园，发现花园里有
𝑛
n 朵美丽值各不相同的花，每朵花的美丽值用
𝑏
𝑖
b
i
​
表示。

Crazy 想让她书房里的布置相较和谐，故对于选择的
𝑘
k 朵花，她将它们按美丽值从小到大排序，得到美丽值数列
𝑎
1
,
…
,
𝑎
𝑘
a
1
​
,…,a
k
​
。

然后她在此束中选了一朵美丽值中等的花（第
⌈
𝑘
2
⌉
⌈
2
k
​
⌉ 朵），设其美丽值为
𝑡
t 。Crazy 定义这束花的不和谐度为
∑
𝑖
=
1
𝑘
(
𝑎
𝑖
−
𝑡
)
2
∑
i=1
k
​
(a
i
​
−t)
2
。

请你帮助 Crazy 选花，使此束花不和谐度最小，并输出这个值。

输入格式
第一行两个正整数
𝑛
,
𝑘
n,k，表示花园里花的数量和 Crazy 想选的花的数量。

第二行
𝑛
n 个互不相同的正整数
𝑏
1
,
…
,
𝑏
𝑛
b
1
​
,…,b
n
​
，表示每朵花的美丽值。

输出格式
一行一个自然数，表示最小的不和谐度。

样例
Input 1
3 2
2 4 5
Output 1
1
Input 2
6 3
9 4 2 5 7 3
Output 2
2
数据范围
本题采用捆绑测试。

Subtask 1（ 10 pts ）：
𝑘
=
1
k=1

Subtask 2（ 10 pts ）：
𝑛
=
𝑘
n=k

Subtask 3（ 20 pts ）：
𝑛
≤
10
n≤10

Subtask 4（ 20 pts ）：
𝑛
≤
8000
n≤8000

Subtask 5（ 40 pts ）：
𝑛
≤
2
×
1
0
5
n≤2×10
5

对于所有数据，
1
≤
𝑘
≤
𝑛
,
3
≤
𝑛
≤
2
×
1
0
5
,
1
≤
𝑏
𝑖
≤
1
0
6
1≤k≤n,3≤n≤2×10
5
,1≤b
i
​
≤10
6

样例解释
在样例 1 中，Crazy 有三种选花方案，分别是 {2, 4}, {2, 5}, {4, 5}，可以算出他们的不和谐度分别是 4, 9, 1，故最小不和谐度为 1。

在样例 2 中，选花方案可以是 {3, 4, 5}，最小不和谐度为 2。

咋写？

Answer 1

引自免费微信小程序：皆我百晓生

为了解决这个问题，我们可以按照以下步骤编写C++代码：

1. 首先读取输入的数字数量n和要选取的花朵数量k。
2. 接着读取每朵花的美丽值，并将其存储在一个数组中。
3. 对美丽值数组进行排序。
4. 计算中位数的位置（根据数组长度是奇数还是偶数确定）。
5. 初始化一个变量用于存储最小的不和谐度，并设置初始值为无穷大。
6. 使用两层循环遍历所有可能的选择组合：外层循环从第一个元素开始到倒数第二个元素（因为我们需要选择k朵花，所以最后一个元素不会被选中）；内层循环则计算当前选择的花朵组合的不和谐度。
7. 在内层循环中，找到中位数位置对应的花朵，然后计算不和谐度。
8. 如果当前不和谐度小于之前记录的最小不和谐度，则更新最小不和谐度。
9. 最后输出最小不和谐度。

以下是完整的C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

int main() {
    int n, k;
    std::cin >> n >> k;

    std::vector<int> flowers(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> flowers[i];
    }

    // 对花的美丽值进行排序
    std::sort(flowers.begin(), flowers.end());

    int min_dissonance = INT_MAX;
    int median_pos;
    if (k % 2 == 0) {
        median_pos = k / 2 - 1;
    } else {
        median_pos = k / 2;
    }

    // 遍历所有可能的选择组合
    for (int i = 0; i <= n - k; ++i) {
        int t = flowers[i + median_pos]; // 当前中位数
        int current_dissonance = 0;

        // 计算当前组合的不和谐度
        for (int j = i; j < i + k; ++j) {
            current_dissonance += pow(flowers[j] - t, 2);
        }

        // 更新最小不和谐度
        if (current_dissonance < min_dissonance) {
            min_dissonance = current_dissonance;
        }
    }

    std::cout << min_dissonance << std::endl;
    
    return 0;
}

这段代码首先读取输入，对花朵的美丽值进行排序，然后找到中位数的位置。接下来，它遍历所有可能的选择组合，并计算每个组合的不和谐度。在每次迭代中，如果遇到更小的不和谐度，就更新最小值。最后，程序会输出最小的不和谐度。