思路

本题核心在于：

• 相同点赞数的 $Plog$ 不能在同一个连续序列中重复出现（因为点赞数唯一性要求），所以同一个点赞值的 $Plog$ 一定会分散到不同收藏夹中
• 收藏夹的连续性要求，意味着我们会按点赞数排序，并将其划分为若干段连续区间
• 每个收藏夹的成本（杂乱度）由该段中最大$c_i$决定

本题为2025年8月20日小红书机考原题

小红书机考的介绍点击这里

题目内容

在小红书$App$中，用户可以创建若干收藏夹来整理$Plog$内容。

现有$n$条$Plog$，每条$Plog$有点赞数量$a_i$和内容杂乱度$c_i$，均为正整数。需要将它们分成若干收藏夹，满 足:

• 每个收藏夹中的$Plog$点赞数量从小到大排序后依次为$s,s+1,...,s+m-1$。

每个收藏夹的杂乱度取决于最大那条$Plog$的内容杂乱度，即该收藏夹内所有$c_i$的最大值。

请计算如何分组，可使全部收藏夹的杂乱度之和最小，并输出该最小值。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≤T≤10^4)$代表测试用例数，每组测试数 据描述如下:

第一行输入一个整数$n(1≤n≤2*1e5)$，表示$Plog$数量。

第二行输入$n$个整数$a_1,a_2,...a_n(1≤a_i≤10^9)$，表示每条$Plog$的点赞数量。

第三行输入$n$个整数$c_2,c_2,...c_n(1≤c_1≤10^9)$，表示每条$Plog$的内容杂乱度。

除此之外，保证单个测试文件的$n$之和不超过$2*10^5$。

输出描述

对于每组测试数据，新起一行输出一个整数，表示全部收藏夹的杂乱度之和的最小值。

样例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

说明

对于第一组测试数据，一种最优分组方案是:

收藏夹一包含$Plog 1,3,6$，其杂乱度为$max (3,2,1)= 3$;

收藏夹二包含 $Plog 2,4,5$，其杂乱度为$max (5,6,4)= 6$;

因此总杂乱度为$3+6=9$