AT_tupc2022_k.Lebesgue Integral

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 $N$ 的正整数序列 $(A_1,A_2,\dots,A_N)$ 。令 $M = \max\,\{A_i \mid 1 \leq i \leq N\}$ ，将区间 $(0,M]$ 分成 $K$ 个区间。也就是说，选择非负实数 $m_i\ (i=0,1,\dots,K)$ ，满足 $0=m_0 < m_1 < m_2 < \dots < m_{K-1} < m_K = M$ ，使得 $(0,M] = (m_0,m_1] \cup (m_1,m_2] \cup \dots \cup (m_{K-1},m_K]$ 。

当区间划分合理时，求
[
\displaystyle \sum_{i=1}^{K} m_i \times (\text{满足 } j \text{ 使得 } A_j \in (m_{i-1}, m_i] \text{ 的 } j \text{ 的个数})
]
的最小值。可以证明答案必然为整数。

输入格式

输入以如下格式从标准输入读入。

$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

请输出一个整数，表示答案。

输入输出样例

输入#1
```
4 2
3 7 4 5
```
输出#1
```
22
```

输入#2

19 4
3279 97197 36049 32099 29257 18290 96531 13435 88697 97081 71483 11396 77398 55303 4166 3906 12281 28658 30496

输出#2

说明/提示

样例解释 1

例如，将 $(0,7]=(0,4]\cup(4,7]$ 分割时，所求值为 $4 \times 2 + 7 \times 2 = 22$ ，且这是最小值。

数据范围

$1 \leq N \leq 10^5$
$1 \leq K \leq 10^5$
$1 \leq A_i \leq 10^5 \quad (i=1,2,\dots,N)$
输入均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页