CF Round: GoodBye2022 题解

参加了孟爷爷的蓝桥杯训练营，奉旨写题解（

本套题是CF的2022告别题，没有现场打，但既然要作为蓝桥杯的练习，那自然要用java多熟悉一下用java来写算法辣（u1s1 用Java写算法是真的蛋疼

经过孟爷爷评测，本场的难度是div1+2，是打不过的难度，尽量看看能做几题

A. Koxia and Whiteboards

Problem - A - Codeforces

题目大意：

有一串n个数字，要进行m次操作，每次操作有一个对应的替换数字，每次操作可以选择一个前者的数字替换为后者。求最后这n个数的总和最大是多少。

数据范围是 $$ n,m≤100，a_i,b_i <10^9$$

思路：

那么一看这个题就是一个贪心，每次只要取原数最小的替换即可。正确性：替换没有后效性（就是说，不存在执行一个非贪心的操作能使得后期能取得比贪心更高的收益），对于每次替换，替换最小的收益一定比替换其他的收益大。

于是代码就出来了，用优先队列动态维护最小值，然后每次都替换最小值就好。复杂度O(NlogN)。

坑：

一看这个题目，就立马按签到题的思路写了，结果没好好读题直接吃亏。首先题目说perform m operations，这里隐含了两个意思：1. 这m个替换必须全部都执行，不能选择性执行；2. 后面说的是the j-th operation，意味着每次替换的顺序已经固定，所以必须按顺序进行替换，不能修改顺序。

与stl不同，java自带的优先队列默认是升序排列。使用poll()方法取出队首并出列，使用peek()方法取出队首而不出列，使用add()方法添加元素。

可以使用自定义比较器的方法来自定义排序的方式：

static Comparator<Integer> cmp = new Comparator<Integer>(){
    public int compare(Integer e1, Integer e2){
        return e2-e1; // 降序
    }
}
...
Queue<Integer> pq = new PriorityQueue<>(cmp);

当然用取负的方法也是可以的。

代码：

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int t;
        Scanner scanner = new Scanner(System.in);
        t = scanner.nextInt();
        while(t>0){
            long tot = 0; long add = 0;
            PriorityQueue<Long> pqa = new PriorityQueue<>();
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            for(int i =1;i<=n;i++){
                long tmp = scanner.nextInt();
                pqa.add(tmp);
                tot+=tmp;
            }
            for(int i =1;i<=m;i++){
                long b = scanner.nextInt();
                add += b-pqa.poll();
                pqa.add(b);
            }
            System.out.println(add+tot);
            t--;
        }
    }
}

B. Koxia and Permutation

Problem - B - Codeforces

题目大意：

给出n和k，求一种[1,n]的排列的构造，使得在宽度为k的窗口（[1,k]，[2,k+1]，…）内最大值和最小值的和最小。

数据范围：$$n,k<2^5$$

思路：

每次k是给定的，那么就是一个标准的滑动窗口。这题是一题构造题，那么我们就应该找到一种通用的规律设置排列。尤其观察样例，发现其实后两个case都是无效样例，说明规律应该是显而易见的。

下面考虑贪心。考虑n=5，k=2，为使min+max最小，我们应当尽量凑【max=一个大值，min=一个小值】这样的组合，例如【5, 1, 4, 3, 2】。最优解就是将最大值放在第一位（使得其只参与一次，当然解法不唯一），然后使得它所在窗口的范围（与k有关）内能包括进最小值（贪心，自然是放在最右边），再放置次大值并根据窗口范围放置次小值，以此类推直到放完。例如n=6，k=3，可构造【6, 5, 1, 4, 3, 2】。由于考虑到了各个窗口位置，容易证明这样一定是最优的。

总结下，我们依次从大到小放置数字，但每次到达窗口边界（i % k == 0）就放置一个小值（从小到大取），其他位置都从大到小放置大值。复杂度为O(n)。

重要：针对Java的优化：

我的解法复杂度为O(n)，面对2e5的数据绰绰有余，于是敲好java代码提交：

import java.util.Scanner;
public class Main {

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t>0){
            int n = scanner.nextInt(); int k = scanner.nextInt();
            int nows = 0, nowb = n+1;
            for(int i = 1;i<=n;i++){
                if(i%k!=0){
                    nowb--;
                    System.out.printf("%d ",nowb);
                }else{
                    nows++;
                    System.out.printf("%d ",nows);
                }
            }
            System.out.print('\n');
            t--;
        }
    }
}

然后愉快的TLE了…

重写了一份C版本的代码，顺利通过，而且在100ms以内。

按理来说Java虽然比C慢，但是计算不应该慢这么多才对。观察本题，发现本题输入输出较多，且输出远大于题目输入，猜测可能是Java的输入输出过于慢导致TLE。

输入优化

要优化输入，可以简单的让Scanner采用BufferedInputStream来读取System.in，而不是直接让Scanner读取它：

Scanner scanner = new Scanner(new BufferedInputStream(System.in));

这样的优化书写简单，并且不用修改后面的Scanner用法。在本题大致可以加快50ms左右。

对于输入还有更深入的优化，也就是使用BufferedReader和StringTokenizer来替代Scanner：

static class FastReader{
       BufferedReader br;
       StringTokenizer st;

       public FastReader(){
           br = new BufferedReader(new
                    InputStreamReader(System.in));
       }

       String next(){
           while (st == null || !st.hasMoreElements()){
               try{
                   st = new StringTokenizer(br.readLine());
               }
               catch (IOException  e){
                   e.printStackTrace();
               }
           }
           return st.nextToken();
       }
       int nextInt(){
           return Integer.parseInt(next());
       }
       long nextLong(){
           return Long.parseLong(next());
       }
       double nextDouble(){
           return Double.parseDouble(next());
       }
       String nextLine(){
           String str = "";
           try{
               str = br.readLine();
           }
           catch (IOException e){
               e.printStackTrace();
           }
           return str;
       }
   }

之后实例化并调用reader.nextInt()等方法即可。这种方法可以在无优化的基础上提高100ms左右。当然，理论上第一种优化方案已经足够。

输出优化

输出可以使用PrintWriter配合OutputStreamWriter来替代System.out。这种方法很好写，而且printwriter实例的用法和System.out类似：

static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
...
out.printf("%d ",nowb);
out.println("hello world");

在本题，简单的输出优化就可以使得TLE->AC(374ms)，可谓重大优化。

AC代码：

import java.io.BufferedInputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args){
        Scanner scanner = new Scanner(new BufferedInputStream(System.in));
        int t = scanner.nextInt();
        while(t>0){
            int n = scanner.nextInt(); int k = scanner.nextInt();
            int nows = 0, nowb = n+1;
            for(int i = 1;i<=n;i++){
                if(i%k!=0){
                    nowb--;
                    out.printf("%d ",nowb);
                }else{
                    nows++;
                    out.printf("%d ",nows);
                }
            }
            out.print('\n');
            out.flush();
            t--;
        }
    }
}