牛客练习赛50C-tokitsukaze and Soldier-(排序+优先队列)

链接：https://ac.nowcoder.com/acm/problem/50439
来源：牛客网

在一个游戏中，tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。
第i个士兵的战力为v[i]，团的战力是团内所有士兵的战力之和。
但是这些士兵有特殊的要求：如果选了第i个士兵，这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵，就没有这个限制。)
tokitsukaze想知道，团的战力最大为多少。

思路：

姑且将s[i]称为容忍度。

如果没有s[i]这个属性，那就是简单贪心。

对容忍度从大到小排序，从前往后遍历，对遍历到的士兵，看看队列中的士兵数量是否小于他的容忍度，如果大于就弹出，弹出士兵肯定是弹出战力低的，保留战力高的，所以队列用优先队列。先遍历到的容忍值肯定比后遍历到的容忍值大，所以每次只需要看当年士兵的容忍值，队列元素数量 满足 当前这个士兵的 必然满足队列里的士兵的容忍值。

import java.util.*;

public class Main{
    static Node[] a=new Node[100005];
    
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        long maxx=-1;
        long sum=0;
        for(int i=0;i<n;i++) {
            a[i]=new Node();
            a[i].v=scan.nextLong();
            a[i].s=scan.nextInt();
        }
        Arrays.sort(a,0,n,new Comparator<Node>() {
            public int compare(Node p1,Node p2) {
                return (int)(p2.s-p1.s);//数组中，容忍度大的放前面
            }
        });
        PriorityQueue<Node> q=new PriorityQueue<Node>(new Comparator<Node>() {
            public int compare(Node p1,Node p2) {
                return (int)(p1.v-p2.v);//战力小的放前面
            }
        }); 
        for(int i=0;i<n;i++) {
            while(q.size()>=a[i].s) {
                sum-=q.poll().v;
            }
            q.add(a[i]);
            sum+=a[i].v;
            maxx=Math.max(maxx, sum);
        }
        System.out.println(maxx);
    }
}

class Node{
    long v;
    int s;
}