Contestant. Rank 3946. Rating +15 (+165 -150).

A. Make it Beautiful

题意

给定一个数组 \(a\)，将其重新排列，使其满足对于任意 \(a_i\)，均满足前缀和 \(sum_{i-1} \neq a_i\)。

思路

将数组降序排列即可。

需要特判一种情况，当降序排列后，第一个数和第二个数重复，那么需要向后枚举，找到第一个不一样的数，将其和第一个数交换即可。若没有这个数，输出 \(NO\)。

时间复杂度：最坏\(O(n)\)

对应AC代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        nxt:while(t -- > 0){
            int n = scanner.nextInt();
            int[] sum = new int[n + 1];
            Integer[] a = new Integer[n];
            for(int i=0;i<n;i++) a[i] = scanner.nextInt();
            Arrays.sort(a, (o1, o2) -> o2 - o1);
            if(a[0] != a[1]){
                System.out.println("YES");
                for(int i=0;i<n;i++) System.out.printf("%d ", a[i]);
                System.out.println();
                continue nxt;
            }
            boolean flag = false;
            for(int i=2;i<n;i++){
                if(a[i] != a[1]){
                    int tmp = a[i]; a[i] = a[1]; a[1] = tmp;
                    flag = true;
                    break;
                }
            }
            if(flag){
                System.out.println("YES");
                for(int i=0;i<n;i++) System.out.printf("%d ", a[i]);
                System.out.println();
            }else System.out.println("NO");
        }
    }

}

签到签到，简单的贪心

B. Matrix of Differences

题意

给定矩阵的规模 \(n\)，构造一个 \(n \times n\) 的矩阵，使所有相邻的 \(x,y\) 的 \(|x-y|\) 值中不同的数值的个数最大。

思路

既然要让不同的差值出现，那么我们可以按照 \(1,n-1,2,n-2,...\) 的方式排列，为了让这个排列的数字能相邻，最简单的方法就是按蛇形排布，输出这个排列即可。

时间复杂度：\(O(n^2)\)

对应AC代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        nxt:while(t -- > 0){
            int n = scanner.nextInt();
            int[][] a = new int[n][n];
            int now = 1;
            boolean flag = true;
            int l = 1, r = n * n;
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    int p = i % 2 == 0 ? j : n - j - 1;
                    a[i][p] = flag ? l ++ : r --;
                    flag = !flag;
                }
            }
            for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++){
                    System.out.printf("%d ", a[i][j]);
                }
                System.out.println();
            }
        }
    }

}

怎么赛时就是想了那么久呢...

C. Yet Another Tournament

题意

给定数组 \(a\)，规定自己和其他的对手的输赢取决于准备时间，如果将要打败的对手的等待时间总和小于等于 \(m\) ，那么判定为获胜。而其他的对手之间的输赢取决于下标，\(i>j\) 时 \(i\) 赢。在允许出现同名次的条件下，打败的对手越多，排名越靠前，输出自己的排名。

思路

我们把这两个类型拆分成两个问题，最后合并在一起：

升序排序准备时间，统计能打败多少人，记为 \(ans\)；
因为 \(ans+1 > ans\)，所以 \(ans+1\) 的排名会更高，所以我们需要将 \(ans+1\) 对应的值替换过来，否则排名会向后移一位。所以我们需要判断 \(ans+1\) 在排序前数组中对应的值是否可以替换掉 \(ans\) 在排序后数组中对应的值，如果不可以，那么将排名后移。

时间复杂度：\(O(n)\)

对应AC代码

import java.util.*;

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(), m = scanner.nextInt();
            int[] a = new int[n + 2], b = new int[n + 1];
            for (int i = 1; i <= n; i++) a[i] = b[i] = scanner.nextInt();
            Arrays.sort(b, 1, n + 1);
            int ans = 0, sum = 0;
            for (int i = 1; i <= n; i++) {
                if(sum + b[i] > m) break;
                sum += b[i];
                ans ++;
            }
            if (sum + a[ans + 1] - b[ans] > m) System.out.println(n - ans + 1);
            else System.out.println(Math.max(n - ans, 1));
        }
    }

}

题目要看清