CFRound-GoodBye2022题解.md

CFRound-GoodBye2022题解.md

tk_sky 38 2023-01-03

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左右。

对于输入还有更深入的优化,也就是使用BufferedReaderStringTokenizer来替代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--;
        }
    }
}