# CFRound-GoodBye2022题解

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

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

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

## A. Koxia and Whiteboards

> [Problem - A - Codeforces](https://codeforces.com/contest/1770/problem/A)

**题目大意**：

有一串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()`方法添加元素。
>
> 可以使用自定义比较器的方法来自定义排序的方式：
>
> ```java
> static Comparator<Integer> cmp = new Comparator<Integer>(){
>     public int compare(Integer e1, Integer e2){
>         return e2-e1; // 降序
>     }
> }
> ...
> Queue<Integer> pq = new PriorityQueue<>(cmp);
> ```
>
> 当然用取负的方法也是可以的。

**代码**：

```java
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](https://codeforces.com/contest/1770/problem/B)

**题目大意：**

给出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代码提交：

```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读取它：

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

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

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

```java
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类似：

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

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

**AC代码：**

```java
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--;
        }
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.mcyou.cc/suan-fa-xiang-guan/ti-jie/cfroundgoodbye2022-ti-jie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.