CF1046F.Splitting money
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
爱丽丝有 n 个账户,为了使自己的财产更分散些,她决定拆分自己的账户,把一些账户中的钱转入新账户,使每个账户中的钱数都不超过 x 个单位货币。每一次转账都需要花费 f 个单位货币的手续费。现在她想知道为了实现她的目标,她至少需要支付多少手续费。
输入格式
第一行有一个整数 n(1≤n≤2×105),代表原来账户的个数。
第二行有 n 个整数 ai(1≤ai≤109),代表爱丽丝原本账户的钱数。
第三行两个整数 x,f(1≤f<x≤109),含义如上。
输出格式
一行一个整数,代表爱丽丝的最少手续费。
输入输出样例
输入#1
3 13 7 6 6 2
输出#1
4
说明/提示
爱丽丝转账的最优转账过程:
- 13 7 6 (开始状态)
- 6 7 6 5 (将 5 个单位货币从第一个账户转向新账户,并且花费 2 个单位货币的手续费)
- 6 4 6 5 1 (将 1 个单位货币从第二个账户转向新账户,也花费两个单位货币的手续费)
两次转账,总手续费为 4 个单位货币。
输入解题思路,AI测评打分。不知道怎么写?