tokitsukaze and Soldier 题解

tokitsukaze and Soldier

https://ac.nowcoder.com/acm/problem/50439

考点：贪心 + 优先队列(PriorityQueue)

读了一遍题目让我想起来了堆，优先队列的数据结构所需要的就是堆，而且不用手写堆emmm。

很容易就可以想到先按s从大到小进行排序。

然后从头开始遍历，先把当前元素v加入queue中，然后判断优先队列中元素是否比s[i]大，大的话就把多余的从queue中扔出；

每次计算sum的值，取最大值就好。

import java.util.*;
import java.math.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.PrintWriter;
public class Main {
    public static void main(String args[])throws IOException
    {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int n = (int)in.nval;
        long v[] = new long[n];
        long s[] = new long[n];
        PriorityQueue<Long> queue = new PriorityQueue<>();
        long sum=0,max=0;
        for(int i=0;i<n;i++)
        {
            in.nextToken();
            v[i] = (long)in.nval;
            in.nextToken();
            s[i] = (long)in.nval;
        }
        long tempss,temp;
        QuickSort(0,n-1,s,v);
        for(int i=0;i<n;i++)
        {
            queue.add(v[i]);
            sum+=v[i];
            if(queue.size()>s[i])
            {
                while(queue.size()>s[i])
                {
                    sum-=queue.peek();
                    queue.poll();
                }
            }
                max = Math.max(max, sum);
        }
        out.println(max);
        out.flush();
    }
   public static void QuickSort(int l,int r,long s[],long v[])
    {
        int i=l,j=r;
        long key = s[(r+l)/2],temp=0;
         
        do{
            while(s[j]<key)
                j--;
            while(s[i]>key)
                i++;
            if(i<=j)
            {
                temp = s[j];
                s[j] = s[i];
                s[i] = temp;
                temp = v[j];
                v[j] = v[i];
                v[i] = temp;
                i++;
                j--;
            }
        }while(i<=j);
        if(l<j) QuickSort(l,j,s,v);
        if(i<r) QuickSort(i,r,s,v);
         
    }
}