113 lines
2.3 KiB
Markdown
113 lines
2.3 KiB
Markdown
# P11309 纷飞的樱花雨
|
||
|
||
## 题目背景
|
||
|
||
高中的时候做过樱花雨实验，氯化钴遇到氢氧化钠溶液产生的沉淀物就像是一场铺天盖地的樱花雨。
|
||
|
||
小 $ \zeta $ 问她，你见过樱花吗？
|
||
|
||
她抬头摇起眼睛，碎亮的光倒映在少女乌黑的瞳孔里。
|
||
|
||
她侧头定定看了我一会儿，然后淡淡地笑了。
|
||
|
||
她说，「我知道你想考武汉大学。」
|
||
|
||
「我也会去武汉大学。」
|
||
|
||
「今年九月，你要和我一起去看樱花吗？」
|
||
|
||
## 题目描述
|
||
|
||
小 $ \zeta $ 喜欢观赏樱花。
|
||
|
||
$ n $ 朵樱花的掉落过程中，第 $ i $ 个掉落的樱花的美丽度为 $ a_i $。
|
||
|
||
每朵樱花掉落后，樱花掉落的总观赏度会增加这朵樱花及之前所有已经掉落的樱花的美丽度的最大值。
|
||
|
||
交换**正好** $ k $ 次两朵樱花的掉落顺序（不能交换一朵樱花和本身，但可以重复交换两朵樱花），最大化总观赏度的值。
|
||
|
||
形式化地讲，给出一个长度为 $ n $ 的数组，进行正好 $ k $ 次交换使得 $ \sum_{i=1}^n \max_{j=1}^ia_j $ 最大。
|
||
|
||
## 输入格式
|
||
|
||
**本题多测**，第一行输入该测试点内数据组数 $ T $。
|
||
|
||
对于每组测试数据：
|
||
|
||
第一行两个整数 $ n $ 和 $ k $，含义见题目描述。
|
||
|
||
接下来 $ n $ 个空格分隔的整数，第 $ i $ 个代表 $ a_i $ 的初始值。
|
||
|
||
## 输出格式
|
||
|
||
对于每组测试数据，输出一行一个整数表示题目要求的值。
|
||
|
||
## 输入输出样例 #1
|
||
|
||
### 输入 #1
|
||
|
||
```
|
||
3
|
||
3 0
|
||
9 8 2
|
||
2 1
|
||
10 11
|
||
5 10
|
||
1 2 3 4 5
|
||
```
|
||
|
||
### 输出 #1
|
||
|
||
```
|
||
27
|
||
22
|
||
25
|
||
```
|
||
|
||
## 输入输出样例 #2
|
||
|
||
### 输入 #2
|
||
|
||
```
|
||
5
|
||
5 0
|
||
100 101 102 103 104
|
||
5 1
|
||
20 40 50 70 10
|
||
2 103
|
||
30 20
|
||
7 2
|
||
1 2 3 4 5 6 7
|
||
2 10
|
||
1 1
|
||
```
|
||
|
||
### 输出 #2
|
||
|
||
```
|
||
510
|
||
350
|
||
50
|
||
49
|
||
2
|
||
```
|
||
|
||
## 说明/提示
|
||
|
||
**【样例 1 解释】**
|
||
|
||
第二组数据可以将 $ 10 $ 和 $ 11 $ 交换，观赏度总和为 $ 11+11=22 $。
|
||
|
||
**【数据规模与约定】**
|
||
|
||
对于 $ 100\% $ 的数据，$ 1 \le T \le 500 $，$ 2 \le n \le 10^5 $，$ 0 \le k \le 10^9 $，$ \sum n \le 10^6 $，$ 1 \le a_i \le 10^9 $。
|
||
|
||
**本题测试点等分，按测试点加和计分。**
|
||
|
||
| 测试点编号 | $ n $ | $ k $ |
|
||
|:-:|:-:|:-:|
|
||
| $ 1 $ | $ \le 50 $ | $ =0 $ |
|
||
| $ 2 $ | - | $ =0 $ |
|
||
| $ 3 \sim 4 $ | $ \le 50 $ | $ =1 $ |
|
||
| $ 5 \sim 7 $ | - | $ =1 $ |
|
||
| $ 8 \sim 10 $ | - | - | |