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);
}
} 
拼多多集团-PDD工作强度 281人发布
查看5道真题和解析