Input
The first line of the input contains integer n (1 ≤ n ≤ 105) — the initial number of legs in the table Arthur bought. The second line of the input contains a sequence of n integers li (1 ≤ li ≤ 105), where li is equal to the length of the i-th leg of the table. The third line of the input contains a sequence of n integers di (1 ≤ di ≤ 200), where di is the number of energy units that Arthur spends on removing the i-th leg off the table.Output
Print a single integer — the minimum number of energy units that Arthur needs to spend in order to make the table stable.Examples
Input 2 1 5 3 2 Output 2 Input 3 2 4 4 1 1 1 Output 0 Input 6 2 2 1 1 3 3 4 3 5 5 2 1 Output 8这题在Codeforces上的标签有brute force、data structures、dp以及greedy。一开始做以为是单纯的区间dp，想破头也没想明白。后来看题解也看得十分懵，自行设计了“再次使用sort()，直接将代价较小的桌腿置于数组前部，从而贪心地锯断这些桌腿”的方案。自觉十分完美，同时判断次数较少，最后结果是超时。我非常懊恼，最终还是强行把桶排序枚举的贪心策略给看明白了，解决了这道题。
简单地说，这题就是要找到一种长度 len ，这种长度的桌腿有 x 根。将 len 作为最终留下的最长桌腿长度，将长度大于 len 的桌腿全部移除，长度等于 len 的全部保留，再额外保留 x−1 根长度小于 len 的任意桌腿（如果长度小于 len 的桌腿有这么多的话），同时确保额外保留的 x−1 根桌腿的锯断代价是长度小于 len 的桌腿中代价最大的那一部分。
假设我们规定最长桌腿长度 len=l ，那么按照上述条件操作，可以确保让桌子以长为 l 的桌腿保持平衡的代价是最小的。亦即我们要在尽量少锯桌腿的情况下保持桌子的平衡，若非锯不可，我们也选择代价小的来锯断。
刚才假设的是一种定长 len=l。那么对于不同的 len ，结果自然会有所不同。这就需要从桌子的最短桌腿枚举到最长桌腿，看看用哪种桌腿来保持平衡可以令总代价最小。
这一题的关键在于 k∈[1,200] 的对代价的枚举。 考虑如下样例（Codeforces test 5）：
桌腿长度56714151617191919代价1957054671401835625132186首先可以看出，必须令 len=19 才可能获得最小代价；而为使代价最小，需要将红色高亮所示的5条桌腿锯断。而本例中最小的代价就是这五个代价之和：387。
如何得出最小代价呢？ 从 len=5 枚举至 len=19 的过程易于理解，主要是在长度小于19的桌腿中保留代价最大的两个桌腿。为达到这一效果，我们需要记录所有长度小于19的桌腿对应的代价，然后令 k∈[1,200] ， k 表示对代价的枚举，从大到小。这样就可以完成按代价从大到小的顺序检查桌腿，保留代价最大的 x−1 条桌腿的过程，从而得出最小代价。
注：代码中的枚举过程显示，对 len=19 的枚举要进行三次，分别对应三个长度为19的桌腿。但最后能确保得到最小代价。原因是：第一次枚举表示三个长为19的桌腿全部保留，额外保留两条长度较短的桌腿；第二次枚举表示保留两个长为19的桌腿，额外保留两条长度不大于19的桌腿；第三次枚举表示保留第三条长为19的桌腿，额外保留两条长度不大于19的桌腿。可以想象，第一次枚举共保留了5条桌腿（长度分别为5,16,19,19,19），第二次枚举共保留了4条桌腿（长度分别为5,19,19,19），第三次枚举保留了三个长为19的桌腿。显然，只有第一次枚举保留的桌腿最多，才可能取得最小代价。
#include <algorithm> #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 1e5+4, INF = 0x7fffffff; int ocur[maxn], allCost[maxn], sumOcur[maxn], sumCost[maxn], barrel[204]; // ocur[]:每种长度的桌腿总数; // allCost[]:每种长度的桌腿的代价总和; // sumOcur[]:桌腿出现次数的前缀和; // sumCost[]:桌腿代价总和的前缀和; // barrel[]:对代价的桶排序。 struct leg{ int len, cost; bool operator < (const leg &a)const{ return len < a.len; } } legs[maxn]; int main(){ #ifdef TEST freopen("test.txt", "r", stdin); #endif // TEST int n; while(cin >> n){ memset(ocur, 0, sizeof(ocur)); memset(allCost, 0, sizeof(allCost)); memset(sumOcur, 0, sizeof(sumOcur)); memset(sumCost, 0, sizeof(sumCost)); memset(barrel, 0, sizeof(barrel)); for(int i = 1; i <= n; i++){ scanf("%d", &legs[i].len); ocur[legs[i].len]++;// 记录某种长度的桌腿总数。 } for(int i = 1; i <= n; i++){ scanf("%d", &legs[i].cost); allCost[legs[i].len]+=legs[i].cost;// 记录某种长度的桌腿的总代价。 } sort(legs+1, legs+1+n);// 按桌腿长度进行排序。 int maxLen = legs[n].len;// 记录桌腿最大长度，用于规定后续枚举的上界。 for(int i = 1; i <= maxLen; i++){// 构造前缀和。 sumOcur[i] = sumOcur[i-1] + ocur[i]; sumCost[i] = sumCost[i-1] + allCost[i]; } int result = INF; for(int i = 1; i <= n; i++){// 枚举最终的最长桌腿长度。 int tempRes = sumCost[maxLen] - sumCost[legs[i].len];// 去掉大于当前枚举值的桌腿所需的代价。 int anotherLeftPart = ocur[legs[i].len] - 1;// 需要格外留下的最大桌腿数量。 for(int k = 200; k >= 1; k--){// 枚举长度小于当前桌腿长度的代价。 if(barrel[k] > 0){ if(barrel[k] <= anotherLeftPart) anotherLeftPart -= barrel[k]; else{ tempRes+=k*(barrel[k] - anotherLeftPart); anotherLeftPart = 0; } } } result = min(result, tempRes); barrel[legs[i].cost]++;// 延迟添加当前桌腿的代价值，确保每次枚举代价时所检查的代价值都属于“长度小于等于当前桌腿”的桌腿的代价。 } cout << result << endl; } return 0; }