题目链接：https://zhixincode.com/contest/3/problem/J?problem_id=43
样例输入 1
4 11
10 1
1 1
10 2
1 2
10 3
1 3
15 4
15 4
15 4
15 4
15 4
样例输出 1
28
题解：
首先是有个简单的想法，假设wls买完后，$n$ 个居民他们的各自的宝物数目最大不超过 $k$，因此wls手里的宝物数目至少要大于 $k$。
所以暴力枚举 $k$，然后再暴力地对所有宝物数目超过 $k$ 的居民，将他们买到不超过 $k$；然后如果此时wls手里的宝物数 $\leq k$ 则再从所有居民的宝物中挑最便宜的买，直到wls的宝物数目大于 $k$ 为止（假设要再买 $e$ 个宝物才行）。
如果是div2的话，由于 $n,m$ 范围小，想到这里就可以直接写了，div1的话还需要考虑优化。
我们知道，如果把居民按宝物数目从大到小排序，并且每个居民的宝物按价值排序（小的放在上面），那么从大到小枚举 $k$ 的时候，就像一把刀一层层的往下压，那么每个居民的宝物局如同一个不规则的楼梯上一层层的被削去，由于宝物数目最多 $m$ 个，因此把这些宝物一点点收入wls的囊中只需要 $O(m)$ 的时间复杂度。
那么，再考虑怎么从居民手里还剩的宝物中，再买 $e$ 个宝物以使wls的宝物数最多，可以用线段树来做，每次已经确定收入wls囊中的宝物都在线段树中标成 $0$，然后在线段树中用数量 $e$ 去查询得到相应的花费。最后维护每个 $k$ 对应的wls总花费的最小值即可。
这样一来，时间复杂度就是 $O(m \log m)$ 的，就不会超时了。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;
#define val(p) (p.first)
#define idx(p) (p.second)
#define mk(x,y) make_pair(x,y)
const ll INF=1e16;
const int maxn=1e5+, maxm=1e5+; int n,m;
vector<P> peo[maxn]; //按居民存储宝物
int rk[maxn]; //按宝物数目存储居民编号
bool cmp(int a,int b) {
return peo[a].size()>peo[b].size();
} P tre[maxm]; //存储所有宝物并排序，并构建相应的线段树
int pos[maxm]; //指出宝物在线段树中的位置 #define ls (rt<<1)
#define rs (rt<<1|1)
struct Node{
int l,r;
ll v; int c;
}o[maxm<<];
void pushup(int rt)
{
o[rt].v=o[ls].v+o[rs].v;
o[rt].c=o[ls].c+o[rs].c;
}
void build(int rt,int l,int r)
{
o[rt].l=l, o[rt].r=r;
if(l==r)
{
o[rt].v=val(tre[l]), o[rt].c=;
return;
}
int mid=(l+r)>>;
build(ls,l,mid), build(rs,mid+,r);
pushup(rt);
}
void update(int rt,int pos)
{
if(o[rt].l==o[rt].r)
{
o[rt].v=, o[rt].c=;
return;
}
int mid=(o[rt].l+o[rt].r)>>;
pos<=mid?update(ls,pos):update(rs,pos);
pushup(rt);
}
ll query(int rt,int k)
{
if(o[rt].l==o[rt].r) return o[rt].v;
if(o[ls].c>=k) return query(ls,k);
else return o[ls].v+query(rs,k-o[ls].c);
} int main()
{
ios::sync_with_stdio();
cin.tie(), cout.tie(); cin>>n>>m;
for(int i=;i<=n;i++) peo[i].clear();
for(int i=;i<=m;i++)
{
ll a; int c; cin>>a>>c;
peo[c].push_back(tre[i]=mk(a,i));
}
for(int i=;i<=n;i++) sort(peo[i].begin(),peo[i].end(),greater<P>());
for(int i=;i<=n;i++) rk[i]=i; sort(rk+,rk+n+,cmp); sort(tre+,tre+m+);
for(int i=;i<=m;i++) pos[idx(tre[i])]=i; //根据原编号得到在线段树中的位置
build(,,m); int ed=;
ll ans=INF;
int acc_tot=; ll acc_cost=;
for(int k=peo[rk[]].size();k>=;k--)
{
for(;ed<=n && peo[rk[ed]].size()>k;ed++);
for(int i=;i<ed;i++)
{
while(peo[rk[i]].size()>k)
{
acc_cost+=val(peo[rk[i]].back());
acc_tot++;
update(,pos[idx(peo[rk[i]].back())]);
peo[rk[i]].pop_back();
}
} ll cost; //wls的总花费
if(acc_tot<=k) cost=acc_cost+query(,min(m,k+-acc_tot));
else cost=acc_cost; ans=min(ans,cost);
}
cout<<ans<<endl;
}