题意：
(n)个物品，每个物品有一个价格，买一个高价格的物品，可以选择免费得到一个价格严格低于这个物品的物品。求得到(n)个物品的最小代价。
题解：
神仙贪心……
题目要求求出最小代价，相当于求最多能免费拿的价格。
先考虑一个(n^2)的DP：将物品按价格从高到低排序。把相同价格的物品放在一起处理。(f[i][j])表示DP到第(i)位，免费拿了(j)个物品，最大能节约的价格。
那么已经原价买了但还没有送东西的物品有(i - 2 * j)个，我们称这些物品为可用物品。
有2种转移：
1，使用可用物品，免费拿当前物品(买一送一)
2，买走一个之前免费拿的物品，用腾出来的可用物品和新买的物品免费拿2个当前物品(买一送二)
但复杂度(n^2),无法通过此题。
现在来考虑优化：
我们对原来的DP数组进行差分得到(g[i][j] = f[i][j] - f[i][j - 1]).
也就是说(g[i][j])表示的不是实际上的值，而是与上一次相比的增量。
既然对于每次转移，我们可以知道相比与上次的增量，那么我们考虑是否可以通过贪心来解决这个问题。
可以发现，(g[i][j])一定单调不增，我们考虑通过3种操作来依次更新(g)数组.(2,3步贪心的正确性是基于已经完成了操作1的基础上的)
1，如果还有多余的可用物品，那么先把当前物品中能免费拿的都拿走。
2，获取(g[i][j - 1])的增量(x),如果(x < val_{now})那么选择不免费拿走带来这个增量(x)的物品(y),我们买走它，因为(x)和腾出来的那个可用物品的价格都严格大于当前物品，因此我们可用最多免费拿2个当前物品放入(g)数组来更新增量，但也有可能只能放入一个，因为当前循环枚举的上限是将之前的所有物品都买下，能够免费拿走多少当前物品，而这个上限可能是奇数，所以在最后面如果拿2个可能就超过上限了。增量即为 免费拿的个数*当前物品价格。
3，增量(x > val_now),那么(x)现在还比较优秀，我们继续选择在(g[i][j - 1])中免费拿走它，但对于(g[i][j]),如果在这个状态中，如果我们选择买走(y),然后用腾出来的物品和(y)免费拿走2个当前物品，是有可能更优的(因为不这么做就无法拿更多的物品)，这样操作带来的增量可以表示为(2 * s[now] - x)，如果这个增量大于0，那么我们选择用这个增量来更新(g[i][j])。
用堆来维护即可。最后的答案即为总价格 - (sum{g[n][j]})(因为在上述转移中，每次转移都只有增量大于0我们才去更新(g)数组，即将真实的(g)数组对0取max了，因此(sum{g[n][j]} = max(f[n][j])))
有一个容易产生疑惑的地方：为什么2中的增量是直接用数量×价格，而3中却要减去上一步的增量(x)呢？
可以观察到，这2个有一个本质上的区别：2虽然修改了(g[i][j - 1]),但从拿物品的方案上而言，是承接了(g[i][j - 2])的，所以不必因为替换了一些物品而减小增量,毕竟(g[i][j - 2])的那个增量是还在的。
而3在更新(g[i][j])的过程中，所使用的方案，和(g[i][j - 1])的方案并不一样，在(g[i][j - 1])中，我们免费拿走了物品(y)，带来了增量(x),而在(g[i][j])中，我们买了物品(y)，失去了增量(x)，这样的话，虽然我们带来了(2 * s[now])的增量，但相对于(f[i][j - 1]),我们的(f[i][j])并没有增加这么多，因此总的增量为(2 * s[now] - x)
如果还有不懂的就看看官方题解 or 代码吧。
我感觉这题的代码应该是比较清晰的。(不喜欢注释的可以把注释删掉再看QWQ)
(如果您觉得我有地方理解错了，还请指出……毕竟这题比较神仙)
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 501000
#define LL long long
int n, tot, sum, rnt;
int cnt[AC], s[AC], tmp[AC];
LL ans;
struct cmp1{bool operator() (int a, int b){return a > b;}};//堆要用小根堆，因为f[j]必定递减,且优先替换便宜的肯定要优一些
inline bool cmp(int a, int b){return a > b;}
priority_queue<int, vector<int>, cmp1> q;
inline int read()
{
int x = 0;char c = getchar();
while(c > '9' || c < '0') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x;
}
void pre()
{
n = read();
for(R i = 1; i <= n; i ++) s[i] = read(), ans += s[i];
sort(s + 1, s + n + 1, cmp);
for(R i = 1; i <= n; i ++)//去重
if(s[i] != s[i + 1]) s[++ tot] = s[i], ++ cnt[tot];
else ++ cnt[tot + 1];
}
LL t[AC], top;
inline void check()
{
top = 0;
while(!q.empty()) t[++ top] = q.top(), q.pop();
for(int i = top; i; i --) printf("%lld ", t[i]), q.push(t[i]);
if(top) printf("
");
else printf("0
");
}
void work()
{
for(R i = 1; i <= tot; i ++)
{
int have = sum - 2 * q.size();//获取现在不做任何修改可以免费送的物品
have = min(have, cnt[i]);//只能放下来取min，因为q.size默认是unsigned int……
for(R j = 1; j <= have; j ++) tmp[++ rnt] = s[i];//先把可以送的直接送了，单独放在一个数组里，防止和之前那些严格比当前大的混在一起
have = min(sum, cnt[i]) - have;//获取最多可以送几个(在当前已经送出一部分的前提下做修改)
for(R j = 1; j <= have; j += 2)//have重新赋值为最多还可以送的个数,因为每次会塞进来2个数，所以每次加2个
{//(min(sum, cnt[i])是把之前的全都买了可以送当前物品的个数，再减去已经送了的)
LL x = q.top(); q.pop();
if(x < s[i])//如果替换掉这一位更优，那么就换掉
{
tmp[++ rnt] = s[i];
if(j < have) tmp[++ rnt] = s[i];//如果j = have,只能说明是奇数，所以不能放第2个进来，，，
}
else//否则的话就维持之前的方案,并且由于无法替换(下一位置是0)，只能尝试买下x，送2个s[j]
{
tmp[++ rnt] = x;//这个也要放到临时数组，，，不然就永远取不出更高的了
if(j < have && 2 * s[i] - x > 0) tmp[++ rnt] = 2 * s[i] - x;//下一状态就买下x，送2 个 s[i],不过如果没有增益的话，还不如不送
}
}
for( ; rnt; -- rnt) q.push(tmp[rnt]);
sum += cnt[i];//获取下一个位置(已处理总数)
// check();
}
while(!q.empty()) ans -= q.top(), q.pop();
printf("%lld
", ans);
}
int main()
{
freopen("in.in", "r", stdin);
pre();
work();
fclose(stdin);
return 0;
}