HBC235254[SCOI2016]萌萌哒,倍增,并查集,数据结构晾衣服题解

把回忆走一遍算法基础篇 2023-11-25 01:20:02 154 0

想要成为编程高手？那就来试试全网最全C++题库，让您在练习中快速成长。

在冬天洗衣服特别是烘干衣服非常困难，但小红是一个非常聪明的女孩，她不怕这个无聊的过程,决定使用散热器来加快干燥速度，但是散热器很小，所以一次只能容纳一件衣服，单位的水，每分钟，每件衣服中含有的水就会减少1单位，当所含的水量变为0时，衣服就算干燥了，当所有衣服都干燥时，烘干过程结束，小红希望在尽可能短的时间内进行烘干，她要求你编写一个程序，用于计算给定衣服的最短烘干时间。

在冬天洗衣服特别是烘干衣服非常困难。但小红是一个非常聪明的女孩。她不怕这个无聊的过程,决定使用散热器来加快干燥速度。但是散热器很小，所以一次只能容纳一件衣服。小红刚洗完 n n件衣服。第 i i件衣服在清洗过程中吸入了 a_i a i 单位的水。每分钟，每件衣服中含有的水就会减少1单位（只有当衣服还没有完全干燥时）。当所含的水量变为0时，衣服就算干燥了。每分钟，小红都可以选择一件衣服在散热器上烘干。散热器非常热，所以在散热器上的衣服的水量每分钟会减小 k k单位（但不会小于0，如果这件衣服含有少于 k k单位的水，则水量将边为0）。当所有衣服都干燥时，烘干过程结束。小红希望在尽可能短的时间内进行烘干。她要求你编写一个程序，用于计算给定衣服的最短烘干时间。