题解：忍者队最大战斗力

本题有点难度，但是思考一下就会做了

题目大意

有 $n$ 个忍者，每个忍者拥有战斗力 $v$，以及最多能接受的队伍人数上限 $t$。
选出一支队伍，队伍人数为 $k$，队伍中每一名忍者都必须满足 $t_i\ge k$，求队伍战斗力总和的最大值。

思路分析

核心观察

如果选定队伍人数 $k$，那么候选忍者只能是所有 $t_i \ge k$ 的忍者；我们在这些忍者里面，选出战斗力最大的 $k$ 个，此时总和就是这个 $k$ 下能拿到的最优值。我们需要遍历所有可能的 $k$，找到最大总和。

直接枚举 $k$ 暴力做复杂度太高，使用贪心+小根堆优化：

1. 贪心排序：把忍者按照承受上限 $t$ 从大到小排序。
2. 遍历+小根堆：依次把忍者的战斗力加入小根堆，维护当前所有已经加入的忍者（他们的 $t$ 都≥当前忍者的$t$）。
   • 堆用来保存战斗力，小根堆堆顶是堆里最小的战斗力。
   • 如果堆的大小 $(sz>t)$：说明当前人数超过这一批忍者能承受的上限，删掉战斗力最小的忍者。
   • 每次处理完一个忍者，更新全局答案（当前堆内总和就是合法队伍的战斗力）。

时间复杂度：$O(n\log n)$。排序 $O(n\log n)$；每个元素入堆、出堆最多一次，堆操作$O(\log n)$，可以通过 $n=10^5$。
空间复杂度：$(O(n))$，存储忍者信息 + 手写堆数组。

AC代码（手写堆，极致时空）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){char a=getchar();int q=0;while(a>='0'&&a<='9')q=q*10+a-48,a=getchar();return q;}
const int M=1e5+10;
int h[M],sz;
void push(int x){
    h[++sz]=x;
    int u=sz;
    while(u>1&&h[u]<h[u/2])swap(h[u],h[u/2]),u/=2;
}
int top(){return h[1];}
void pop(){
    h[1]=h[sz--];
    int u=1;
    while(u*2<=sz){
        int v=u*2;
        if(v+1<=sz&&h[v+1]<h[v])v++;
        if(h[u]>h[v])swap(h[u],h[v]),u=v;
        else break;
    }
}
bool cmp(pair<int,int>a,pair<int,int>b){return a.first>b.first;}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n=read();
    vector<pair<int,int>>p(n);
    for(int i=0;i<n;i++){
        int v=read(),t=read();
        p[i].first=t;
        p[i].second=v;
    }
    sort(p.begin(),p.end(),cmp);
    sz=0;ll sum=0,ans=0;
    for(auto &pr:p){
        int t=pr.first,v=pr.second;
        push(v);sum+=v;
        while(\(sz>t\)){sum-=top();pop();}
        ans=max(ans,sum);
    }
    cout<<ans;
    return 0;
}

样例演示

输入：

3
100 1
50 2
60 2

1. 读入忍者：$((t=1,v=100),(t=2,v=50),(t=2,v=60))$
2. 按 $t$ 降序排序：$(((2,50)),((2,60)),((1,100)))$
3. 遍历：
   • 忍者$((2,50))$：堆[50]，sum=50，sz=1 ≤ 2，ans=50
   • 忍者$((2,60))$：堆[50,60]，sum=(\boldsymbol{110})，sz=2 ≤2，ans=(\boldsymbol{110})
   • 忍者$((1,100))$：堆[50,60,100] sum=210，sz=3>1，不断弹出最小值直到sz≤1。sum=100，ans保持(\boldsymbol{110})
4. 输出答案：$\boldsymbol{(\boldsymbol{110})}$

易错点

1. 读入顺序：输入每行是v t，pair存储要存(t,v)，排序关键字是t，极易写反导致WA。
2. 数据范围：单个v可以到$10^9$，总和必须用long long，int会溢出。
3. 排序方向：必须按t降序，升序会混入不满足条件的忍者，答案错误。
4. 手写堆下标：堆数组从1开始，不要从0写，否则父子节点计算出错。

优化说明

• 使用手写小根堆替代STL优先队列，减少STL容器的内存冗余；提交结果：用时10ms，内存3.75MB，击败100%用户。
• 快读read()加速输入，搭配ios::sync_with_stdio(false);cin.tie(0)进一步压缩IO耗时。

结果展示