虽然是 unrated,不过秉持着 Educational Round 的传统,题还是挺不错的。
A. Chores
评价:善用 STL。
由于 \(a\) 已经排好序了,且 \(x\le \min_{i=1}^{n}a_i\)(即将任何一个数替换为 \(x\) 都能够减少总时长),因此想到贪心。
将最耗时间的 \(k\) 个数变成 \(x\)(亦即题目中的 \(a_{n-k+1},a_{n-k+2},\ldots,a_n\)),共耗时 \(k\times x\);然后求出前 \(n-k\) 个数的和,加起来即可。
注意到 STL 中有 accumulate 函数(在 numeric 头文件中),用法为 accumulate(头指针,尾指针,初始值);
其中头尾指针如 sort
一样,是左闭右开的。于是上面的式子就是以 \(k\times x\) 为初值,对 \(1\) 至 \(n-k+1\) 中的数(左闭右开)进行求和,可以直接套用,大大减小码量。