0%

Codeforces - Educational Codeforces Round 141

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

A. Make it Beautiful

题意

给定一个数组 ,将其重新排列,使其满足对于任意 $aisum{i-1} \neq a_i$。

思路

将数组降序排列即可。

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

时间复杂度:最坏

对应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

题意

给定矩阵的规模 ,构造一个 的矩阵,使所有相邻的 值中不同的数值的个数最大。

思路

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

时间复杂度:

对应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

题意

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

思路

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

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

时间复杂度:

对应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));
        }
    }

}

题目要看清