CF1310A Recommendations

VK 新闻推荐系统每天会为每位用户从 $n$ 个互不相交的类别中各选出一些有趣的文章。每篇文章恰好属于一个类别。对于每个类别 $i$，批处理算法会选出 $a_i$ 篇文章。 最新的 A/B 测试表明，如果每日推荐中每个类别的文章数都不相同，用户会更积极地阅读推荐的文章。定向算法可以在 $t_i$ 秒内为第 $i$ 类找到一篇有趣的新文章。 你需要计算，为了让所有类别的文章数都不相同，最少需要多少总时间来用定向算法为某些类别补充文章？你不能移除批处理算法已经推荐的文章。

输入的第一行包含一个整数 $n$，表示新闻类别的数量（$1 \le n \le 200\,000$）。 输入的第二行包含 $n$ 个整数 $a_i$，表示批处理算法为第 $i$ 类选出的文章数量（$1 \le a_i \le 10^9$）。 输入的第三行包含 $n$ 个整数 $t_i$，表示定向算法为第 $i$ 类找到一篇新文章所需的时间（$1 \le t_i \le 10^5$）。

输出一个整数，表示为了消除类别间文章数的重复，定向算法所需的最小总时间。

在第一个样例中，可以为第二类补充三篇文章，总共需要 6 秒。 在第二个样例中，所有新闻类别的文章数本就各不相同。 由 ChatGPT 4.1 翻译