CF1046F.Splitting money

普及/提高-

通过率:0%

AC君温馨提醒

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

题目描述

爱丽丝有 nn 个账户,为了使自己的财产更分散些,她决定拆分自己的账户,把一些账户中的钱转入新账户,使每个账户中的钱数都不超过 xx 个单位货币。每一次转账都需要花费 ff 个单位货币的手续费。现在她想知道为了实现她的目标,她至少需要支付多少手续费。

输入格式

第一行有一个整数 n(1≤n≤2×105)n(1 \le n \le 2 \times10^5),代表原来账户的个数。

第二行有 nn 个整数 ai(1≤ai≤109)a_i(1 \le a_i \le 10^9),代表爱丽丝原本账户的钱数。

第三行两个整数 x,f(1≤f<x≤109)x,f (1 \le f<x \le10^9),含义如上。

输出格式

一行一个整数,代表爱丽丝的最少手续费。

输入输出样例

  • 输入#1

    3
    13 7 6
    6 2
    

    输出#1

    4
    

说明/提示

爱丽丝转账的最优转账过程:

  1. 13 7 6 (开始状态)
  2. 6 7 6 5 (将 55 个单位货币从第一个账户转向新账户,并且花费 22 个单位货币的手续费)
  3. 6 4 6 5 1 (将 11 个单位货币从第二个账户转向新账户,也花费两个单位货币的手续费)

两次转账,总手续费为 44 个单位货币。

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

首页