102814: [AtCoder]ABC281 E - Least Elements
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $500$ points
Problem Statement
You are given an integer sequence $A = (A_1, \dots, A_N)$ of length $N$, and integers $M$ and $K$.
For each $i = 1, \dots, N - M + 1$, solve the following independent problem.
Find the sum of the first $K$ values in the sorted list of the $M$ integers $A_i, A_{i + 1}, \dots, A_{i + M - 1}$ in ascending order.
Constraints
- $1 \leq K \leq M \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Let $\mathrm{answer}_k$ be the answer to the problem for $i = k$, and print them in the following format:
$\mathrm{answer}_1$ $\mathrm{answer}_2$ $\ldots$ $\mathrm{answer}_{N-M+1}$
Sample Input 1
6 4 3 3 1 4 1 5 9
Sample Output 1
5 6 10
- For $i = 1$, sorting $A_i, A_{i+1}, A_{i+2}, A_{i+3}$ in ascending order yields $1, 1, 3, 4$, where the sum of the first three values is $5$.
- For $i = 2$, sorting $A_i, A_{i+1}, A_{i+2}, A_{i+3}$ in ascending order yields $1, 1, 4, 5$, where the sum of the first three values is $6$.
- For $i = 3$, sorting $A_i, A_{i+1}, A_{i+2}, A_{i+3}$ in ascending order yields $1, 4, 5, 9$, where the sum of the first three values is $10$.
Sample Input 2
10 6 3 12 2 17 11 19 8 4 3 6 20
Sample Output 2
21 14 15 13 13
Input
题意翻译
### 【题目描述】 给定一个序列 $A$，对于每个 $1 \le i \le N - M + 1$，将 $A_i A_{i + 1} \cdots A_{i + M - 1}$ **从小到大**排序后（不影响原序列），求出 $\mathrm{ans}_i = \sum\limits_{i=1}^{K}A_i$。 ### 【输入格式】 > $N, M, K\\ A_1 A_2 \cdots A_N$ ### 【输出格式】 > $\mathrm{ans}_1 \mathrm{ans}_2 \cdots \mathrm{ans}_{N-M+1}$ ### 【数据范围】 $1 \le K \le M \le N \le 2 \times 10^5$ $1 \le A_i \le 10^9$Output
分数：500分
问题描述
给你一个长度为 $N$ 的整数序列 $A = (A_1, \dots, A_N)$，以及两个整数 $M$ 和 $K$。
对于每个 $i = 1, \dots, N - M + 1$，解决以下独立问题。
找到升序排列的整数序列 $A_i, A_{i + 1}, \dots, A_{i + M - 1}$ 中前 $K$ 个值的和。
约束条件
- $1 \leq K \leq M \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$
- 输入中的所有值都是整数。
输入
输入将从标准输入中给出以下格式：
$N$ $M$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$
输出
设 $\mathrm{answer}_k$ 是对于 $i = k$ 的问题的答案，以以下格式打印它们：
$\mathrm{answer}_1$ $\mathrm{answer}_2$ $\ldots$ $\mathrm{answer}_{N-M+1}$
样例输入 1
6 4 3 3 1 4 1 5 9
样例输出 1
5 6 10
- 对于 $i = 1$，将 $A_i, A_{i+1}, A_{i+2}, A_{i+3}$ 按升序排序得到 $1, 1, 3, 4$，其中前三个值的和为 $5$。
- 对于 $i = 2$，将 $A_i, A_{i+1}, A_{i+2}, A_{i+3}$ 按升序排序得到 $1, 1, 4, 5$，其中前三个值的和为 $6$。
- 对于 $i = 3$，将 $A_i, A_{i+1}, A_{i+2}, A_{i+3}$ 按升序排序得到 $1, 4, 5, 9$，其中前三个值的和为 $10$。
样例输入 2
10 6 3 12 2 17 11 19 8 4 3 6 20
样例输出 2
21 14 15 13 13