「ROI 2022 Day2」最大化收益

ID: 2112

传统题

1000ms

512MiB

难度: (无)

上传者:

标签>

ROI

2022

题目描述

译自 ROI 2022 Day2 T1. Максимизация выигрыша

给定一个由 $n$ 个十进制数字组成的非负整数 $x$ 。你可以任意次数交换相邻的两个数字。每次交换有一个代价 $y$ 。交换完成后，会根据得到的新数字 $x_{new}$ 计算奖金。因此，如果经过 $k$ 次交换得到数字 $x_{new}$ ，收益为 $x_{new} - ky$ 。

我们称数字 $x_{new}$ 为最优数字，如果它是通过交换得到的，并且可以实现最大可能的收益。

根据给定的 $x$ 和 $y$ ，确定最优数字中最大的一个。

第一行给出一个由 $n$ 个十进制数字组成的整数 $x\ (1 \le n \le 10^5)$ 。数字 $x$ 可以有前导零。

第二行给出一个整数 $y\ (1 \le y \le 10^{16})$ ，表示每次交换的代价。

输出一个整数 $x_{new}$ ，表示最优数字中最大的一个。数字 $x_{new}$ 的长度应为 $n$ ，并且可以包含前导零。

170
15

在第一个样例中，交换数字 $1$ 和 $7$ 后得到数字 $710$ ，收益为 $710 - 15 = 695$ 。

170
600

在第二个样例中，不交换数字更有利，收益为 $170$ 。如果交换，收益将为 $710 - 600 = 110 < 170$ 。

314599
17713

001
1000

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	$n$ 的限制	$y$ 的限制	附加限制	子任务依赖
$1$	$27$	$n \le 9$	$y \le 10^8$		$0$
$2$	$13$	$n \le 20$	$y \le 10^8$		$0, 1$
$3$	$19$	$n \le 10^5$	$y = 1$
$4$	$25$		$y \le 10^8$	$x$ 的所有数字均为 $1$ 或 $2$
$5$	$8$		$y \le 10^8$		$0, 1-4$
$6$	$8$		$y \le 10^{16}$		$0, 1-5$