笔试练习2分享（破防彩笔版）

比赛上分（炸鱼圈）

有一款著名的大型多人电子竞技游戏网站“喜爱福”，网站通常会举办一些比赛。通常一名参赛选手只有一个账号，但不难猜到，总会有人“开小号”上分。 某炸鱼就是一位该游戏的忠实玩家，他总共有 𝑛 个账号，每个账号的分数分别为 𝑎𝑖。 他深谙游戏中一位著名玩家 stlk 的一句名言：“只要你永远打分更低的号，那么你的 𝑚𝑎𝑥𝑅𝑎𝑡𝑖𝑛𝑔单调不降”。（𝑚𝑎𝑥𝑅𝑎𝑡𝑖𝑛𝑔指一名玩家分最高的账号的分数） 现在我们记录了炸鱼 𝑚 次的比赛记录，已知炸鱼每次都会谨记 stlk 的名言，从而使用分数最低的账号参赛，现在我们想知道炸鱼每次参赛后，他的 𝑚𝑎𝑥𝑅𝑎𝑡𝑖𝑛𝑔是多少，请你编写代码来算算吧。

输入包含三行。

第一行两个正整数n,m(1≤n,m≤10°)，分别表示炸鱼的账号个数，和炸鱼新参加的比赛记录数。

第二行n个整数a(0＜a＜10°)，表示炸鱼每个账号目前的分数。

第三行m个整数(0≤b;≤10°)，分别表示炸鱼每次比赛后，分数的变化值。

（例如如果炸鱼使用分数为∞的账号参赛，那么他在参加完第j场比赛后，该账号分数会变为+bj。）

输入例子：5 6

1145 1500 1600 1538 1222

10 400 500 1000 2000 10000

输出例子：1600

1600

1722

2500

3538

11555

例子说明： 共比赛了6场，每场赛后都输出炸鱼当前分数最高的分数，如样例所示，前两场比赛后炸鱼分数为1145的账号涨到了1555，因此第三场比赛使用当前分数最低的1222参赛，涨了500分变为1722，成为炸鱼分数最高的账号，因此第三场赛后输出1722。

个人思路：每次都用最小rating账号，构建一个最小堆给rating排个序，同时找到当前账号最大rating，之后从堆顶出堆加上炸鱼后的分数，与当前的最大raing比较更新最大rating。

import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
   int n = in.nextInt();
   int m = in.nextInt();
   int[] a=new int[n];
  for(int i=0;i<n;i++){
      a[i]=in.nextInt();
  }
  int[] b=new int[m];
  for(int i=0;i<m;i++){
      b[i]=in.nextInt();
  }
    PriorityQueue<Integer> pq=new PriorityQueue<>();
  int max=a[0];
  for(int i=0;i<n;i++){
      pq.add(a[i]);
      if(a[i]>max){
          max=a[i];
      }
  }
  for(int i=0;i<m;i++){
      int cur=pq.poll()+b[i];
      if(cur>max){
      max=cur;
      }
      pq.offer(cur);
      System.out.println(max);
  }
}

}

初始化堆：O(n log n)

每场比赛操作：O(log n)（堆的插入和弹出）

总体复杂度：O(n log n + m log n)

菜鸡难得舒服一次，泪目。不练这些类似洛谷那种ACM笔试单纯做leetcode简化过题目的真的很不适应。