(COCI 2023/2024 5) Rolete

题解

题意

给定一个长度为$n$序列。存在以下两种操作

$1.$选择序列中的一个值减$1$代价为$t$

$2.$将所有值减$1$代价为$s+k \cdot r$,其中$r$表示序列中$\leq 0$的数的个数

给定$q$次询问，每次询问给定一个$h$，求使序列中任意值$\leq h$的最小代价

范围 $1 \leq n,s,q,h \leq 10^5,0 \leq k \leq 10^5$

解法

考虑一种贪心

从高到低枚举$h$,每次记录