0820字节笔试

记忆版

Q1

import java.util.Arrays;
import java.util.Scanner;

public class P1 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        while (t-- > 0) {
            int n = scan.nextInt(), k = scan.nextInt(), a1 = scan.nextInt(), a2 = scan.nextInt(), a3 = scan.nextInt();
            int[] arr = new int[]{a1, a2, a3};
            Arrays.sort(arr);
            int gap1 = arr[1] - arr[0], gap2 = arr[2] - arr[1], gap3 = n - arr[2] + arr[0];
            if (n / 3 < k) System.out.println(-1);
            else {
                long ans = 0;
                if (gap1 < k) ans += k - gap1;
                if (gap2 < k) ans += k - gap2;
                if (gap3 < k) ans += k - gap3;
                System.out.println(ans);
            }
        }
    }
}

Q2

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

public class P2 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[2] == y[2] ? x[0] - y[0] : x[2] - y[2]);
        for (int i = 0; i < n; i++) pq.offer(new int[]{scan.nextInt(), scan.nextInt(), scan.next().charAt(0)});
        long ans = 0;
        while (pq.size() >= 5) {
            int[][] arr = new int[5][];
            arr[0] = pq.poll();
            int min = arr[0][1];
            boolean flag = true;
            for (int i = 1; i < 5 && flag; i++) {
                if (pq.peek()[2] != arr[0][2] || pq.peek()[0] != arr[i - 1][0] + 1) flag = false;
                else {
                    arr[i] = pq.poll();
                    min = Math.min(min, arr[i][1]);
                }
            }
            if (flag) {
                int idx = 0;
                for (int i = 0; i < 5; i++) {
                    arr[i][1] -= min;
                    if (arr[i][1] == 0) idx = i;
                }
                ans += min;
                for (int i = idx + 1; i < 5; i++) pq.offer(arr[i]);
            }
        }
        System.out.println(ans);
    }
}

Q3

import java.util.Arrays;
import java.util.Scanner;

public class P3 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = scan.nextInt();
        }
        // 1 2 2 2 4 5
        Arrays.sort(array);
        int[] nums1 = Arrays.copyOf(array, n - 1);
        int[] nums2 = Arrays.copyOfRange(array, 1, n);
        System.out.println(Math.min(solve(nums1, array[n - 1]), solve(nums2, array[0])));
    }

    public static long solve(int[] array, int num) {
        int n = array.length;
        long avg1 = array[Math.max(0, n / 2 - 1)], avg2 = array[n / 2], avg3 = array[Math.min(n / 2 + 1, n - 1)];
        long ans1 = 0, ans2 = 0, ans3 = 0;
        for (int j : array) {
            ans1 += Math.abs(avg1 - j);
            ans2 += Math.abs(avg2 - j);
            ans3 += Math.abs(avg3 - j);
        }
        if (avg1 == num) ans1++;
        if (avg2 == num) ans2++;
        if (avg3 == num) ans3++;
        return Math.min(ans1, Math.min(ans2, ans3));
    }
}

Q4

import java.util.Scanner;

public class P4 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long[] dp = new long[n];
        char[] arr = scan.next().toCharArray();
        long ans;
        ans = dp[0] = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] == arr[i - 1]) dp[i] = dp[i - 1] + 1;
            else dp[i] = dp[i - 1] + i + 1;
            ans += dp[i];
        }
        System.out.println(ans);
    }
}