tokitsukaze and Soldier

思路

这题的话，我觉得用堆来实现最为方便，这题的数据量为,那么配合堆，时间复杂度是，时间上是ok的。
大概思路就是，首先在读入数据的时候，就把最大s和最小s保存下来，然后从大到小遍历，求每一个s对应选取的最大战斗力和，如果要选取s人，那么就把s[i]>=s的人放进堆里面去，然后限制堆的容量是s，并动态求堆的和，在放入堆的时候，sum += v[i],如果堆的容量已经大于s，就pop，并sum -= q.pop();
这题我觉得最核心的是，假如s[i] < s[i+1],那么在求s[i+1]能选取的最大战斗力和之后，再计算s[i]能选取的最大战斗力和是可以在s[i+1]的基础上进行增删。

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int N;
ll res;
struct node{
    int v,s;
    bool operator < (const node &o)const{
        return s<o.s;
    }
}arr[maxn];
priority_queue<int,vector<int>,greater<int> > q;
int main(){
    cin>>N;
    int l = 1e9,r = 0; //记录最小s和最大s
    for(int i = 0;i<N;i++){
        scanf("%d %d",&arr[i].v,&arr[i].s);
        l = min(l,arr[i].s),r = max(r,arr[i].s);
    }
    sort(arr,arr+N);
    ll sum = 0,tail = N-1;//我是倒着循环的
    for(int i = r;i>=l;i--){ //倒着循环我觉得方便些
        while(arr[tail].s >= i){ //只让堆存i个以内的个数，并动态求和
            q.push(arr[tail].v);
            sum += arr[tail].v;
            while(q.size() > i){
                int t = q.top();q.pop();
                sum -= t;
            }
            tail--;
        }
        res = max(res,sum);
    }
    cout<<res<<endl;
    return 0;
}