Description
有一张桌子，有(n)个腿。第(i)根腿的长度是(l_i)。
现在要拿掉一些腿，使得桌子稳定，拿掉第(i)根腿需要(d_i)的能量。
稳定的条件是，假如拿掉若干条腿之后，桌子还有(k)个腿，那么长度最长的腿的数目要超过一半。比如桌子有(5)根腿，那么至少要有(3)根腿是最长的。另外，只有一根腿的桌子是稳定的，两个腿的桌子想要稳定，必需长度是一样的。
你的任务是拿掉若干腿，使得桌子稳定，并且所消耗的能量要最少。
Solution
我们可以枚举桌腿最长的长度是什么，设其为(l_{mx})，然后有(t)根的(l_i=l_{mx})，那么保留的最大能量就是(sumlimits_{l_i=l_{mx}}d_i)，加上长度小于它的桌腿中，选最大的(t-1)根的能量之和（因为要最大化保留的，才能最小化消耗的）。
考虑我们从小到大枚举(l_{mx})，处理这个长度后再把所有满足(l_i=l_{mx})的(d_i)加入当前序列中，那么现在要解决的问题就是要动态维护序列前(t-1)大之和。而对顶堆可以很方便解决这类动态求第(k)大或前(k)大的问题。
对顶堆就是维护两个堆，一个大根堆(q_1)，一个小根堆(q_2)，然后保证(q_2)里的所有元素都大于(q_1)里的，不满足就不断一个(pop())，一个(push(top()))。
我们再保证(q_2.size()=t-1)，那这道题的前(t-1)大之和就是(q_2)内元素之和了。
这个是很难被卡的，因为单次操作次数取决于(|t_i-t_{i-1}|)，最大也就是(n)，复杂度其实和线段树一样也是(nlog(n))。
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, m, sz[100005], l[100005], d[100005];
vector < int > g[100005];
ll mx, s0, sum, s[100005];
priority_queue < int > q1;
priority_queue < int, vector < int > , greater < int > > q2;
int read()
{
int x = 0, fl = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') fl = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();}
return x * fl;
}
int main()
{
n = read();
for (int i = 1; i <= n; i ++ )
l[i] = read(), m = max(m, l[i]);
for (int i = 1; i <= n; i ++ )
d[i] = read(), sum += (ll)d[i];
for (int i = 1; i <= n; i ++ )
{
g[l[i]].push_back(d[i]);
s[l[i]] += (ll)d[i];
sz[l[i]] ++ ;
}
for (int i = 1; i <= m; i ++ )
{
if (!sz[i]) continue;
ll cnt = s[i];
while ((int)q2.size() != sz[i] - 1)
{
if ((!q1.size()) && (!q2.size())) break;
while (q2.size() < sz[i] - 1)
{
int x = q1.top();
q1.pop();
q2.push(x);
s0 += x;
}
while (q2.size() > sz[i] - 1)
{
int x = q2.top();
q2.pop();
q1.push(x);
s0 -= x;
}
}
mx = max(mx, cnt + s0);
for (int p = 0; p < (int)g[i].size(); p ++ )
{
int x = g[i][p];
if (q1.size() && x > q1.top()) q2.push(x), s0 += x;
else q1.push(x);
}
}
printf("%lld
", sum - mx);
return 0;
}