P4362.【贪心11】收藏夹杂乱度
本题为2025年8月20日小红书机考原题
小红书机考的介绍点击这里
题目内容
在小红书App中，用户可以创建若干收藏夹来整理Plog内容。
现有n条Plog，每条Plog有点赞数量ai和内容杂乱度ci，均为正整数。需要将它们分成若干收藏夹，满
足:
- 每个收藏夹中的Plog点赞数量从小到大排序后依次为s,s+1,...,s+m−1。
每个收藏夹的杂乱度取决于最大那条Plog的内容杂乱度，即该收藏夹内所有ci的最大值。
请计算如何分组，可使全部收藏夹的杂乱度之和最小，并输出该最小值。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数T(1≤T≤104)代表测试用例数，每组测试数
据描述如下:
第一行输入一个整数n(1≤n≤2∗1e5)，表示Plog数量。
第二行输入n个整数a1,a2,...an(1≤ai≤109)，表示每条Plog的点赞数量。
第三行输入n个整数c2,c2,...cn(1≤c1≤109)，表示每条Plog的内容杂乱度。
除此之外，保证单个测试文件的n之和不超过2∗105。
输出描述
对于每组测试数据，新起一行输出一个整数，表示全部收藏夹的杂乱度之和的最小值。
样例1
输入
2
6
2 2 3 4 3 1
3 5 2 6 4 1
5
5 6 7 8 9
5 4 3 2 1
输出
9
5
说明
对于第一组测试数据，一种最优分组方案是:
收藏夹一包含Plog1,3,6，其杂乱度为max(3,2,1)=3;
收藏夹二包含 Plog2,4,5，其杂乱度为max(5,6,4)=6;
因此总杂乱度为3+6=9
