本题使用线性扫描算法。
只需要遍历一次所有石子堆,对于每一堆石子数量 ai:
如果 ai>x,说明这堆满足条件,需要拿走 y 颗石子;
否则不拿。
有 n 堆石子。你只做一次统计:对每一堆,如果这堆石子的数量严格大于 x,你就从这堆里拿走 y 颗石子;否则这堆不拿。请计算你一共会拿走多少颗石子。
一行输入三个整数 n,x,y(1≤n≤2×105,1≤y≤x≤109)。
接下来一行输入 n 个整数 a1,a2,…,an(1≤ai≤109),表示第 i 堆的石子数量。
输出一个整数,表示总共拿走的石子数量。
输入
5 3 2
1 3 4 5 3
输出
4
说明
共有 5 堆,阈值为 x=3,每次从满足条件的堆拿 y=2 颗。第 3 堆数量 4>3 拿走 2 颗,第 4 堆数量 5>3 拿走 2 颗,其余三堆数量不严格大于 3 都不拿,共拿走 4 颗。