Contestant. Rank 3574. Rating +50 (+400 -350).

A. Hall of Fame

题意

给定一个只有 L 和 R 的长度为 n 的字符串，对于第 i 个字符，L 表示将 [1,i−1] 照亮，R 表示将 [i+1,n] 照亮。对于该字符串，允许选择一个 i，将 i 和 i+1 对应的字符交换，该操作最多可执行一次。判断是否可以将所有点照亮。若无需交换，输出 0；若交换后才满足条件，输出 i；若无法满足条件，输出 −1。

思路

很显然，只要出现 R,...,L 的排列，就一定可以满足条件。

那么，我们首先可以寻找第一个 R 之后有没有 L，只要找到了 L 就直接输出 0 即可。

否则，我们就需要寻找 LR，并将其交换，并输出 L 对应的下标。

否则，输出 −1 即可。

时间复杂度：O(n)

对应AC代码

Java
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();
            char[] a = scanner.next().toCharArray();
            int l = 0, r = 0, lr = -1;
            boolean preR = false;
            for(int i=0;i<a.length;i++){
                if(i < a.length - 1 && lr == -1 && a[i] == 'L' && a[i + 1] == 'R') lr = i + 1;
                if(a[i] == 'R') preR = true;
                else if(preR){
                    System.out.println(0);
                    continue nxt;
                }
            }
            System.out.println(lr);
        }
    }
}

简单思维题

B. MKnez's ConstructiveForces Task

题意

给定数组的长度 n，构造一个非零数组 s，满足对于任何 i∈[1,n)，有 s1+s2+...+sn=si+si+1。若不可构造，输出 NO，否则输出 YES，以及所构造的数组。

思路

将等式右边移到左边，那么我们只需满足任意取出两个数后数组的和都为 0 即可。那么很显然，当 n 为偶数时，我们只需构造一个 1,−1,1,−1,... 的数组即可。

而当 n 为奇数的时候，既然等式左边有 n 项，而右边有 2 项，若仍然考虑相邻数的和相等的构造方式的话，我们不妨让这个相等的和为 1，这样的话，式子将会变为 sx+n2=1，那么多出来的项 sx 即为 1−n2 。因而，令 w=n2，我们只需构造 1−w,w,1−w,w,1−w,... 即可。

时间复杂度：O(n)

对应AC代码

Java
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();
            if(n == 3) System.out.println("NO");
            else{
                System.out.println("YES");
                if(n % 2 == 0){
                    for(int i=0;i<n/2;i++) System.out.print("1 -1 ");
                }else{
                    int w = n / 2;
                    System.out.printf("%d ", 1 - w);
                    for(int i=0;i<n/2;i++) System.out.printf("%d %d ", w, 1 - w);
                }
                System.out.println();
            }
        }
    }
}

既然是成对的，那就让和也成对呗

C. Least Prefix Sum

题意

给定一个数组 a，定义一次操作为任取一个数并将其改为它的相反数。输出最少的操作数，使 a 的前 m 项和为 a 的所有前 k 项和（k∈[1,n]）中的最小值。

思路

对于题给式子 a1+a2+...+ak≥a1+a2+...+am，

当 k≤m 时，将不等式左边移到右边，我们可以得到第一个条件：以 m 为结尾的不包括 a1 的后缀和均为非正数。

同理，当 k≥m 时，将不等式右边移到左边，我们可以得到第二个条件：以 m+1 为第一项的前缀和均为非负数。

因为上述两者差不多，我们不妨来考虑前者。

显然，在遍历所有后缀和的时候，我们不可以在发现某一项不满足时直接把这一项取相反数，因为我们不能保证后面的项比这一项小，而将最大值取反才是最优解。

因此，为了每次查询的复杂度降到一个合理的值，我们可以采用优先队列。

时间复杂度：O(nlog⁡n)

对应AC代码

Java
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();
            long[] a = new long[n + 1];
            for(int i=1;i<=n;i++) a[i] = scanner.nextInt();
            PriorityQueue<Long> positive = new PriorityQueue<>((o1, o2) -> Math.toIntExact(o2 - o1));
            PriorityQueue<Long> negative = new PriorityQueue<>(Comparator.comparingLong(o -> o));
            long cnt = 0, sum = 0;
            for(int i=m;i>=2;i--){
                sum += a[i];
                if(a[i] > 0) positive.offer(a[i]);
                while(sum > 0) {
                    sum -= 2 * positive.poll();
                    cnt ++;
                }
            }
            sum = 0;
            for(int i=m + 1;i<=n;i++){
                sum += a[i];
                if(a[i] < 0) negative.offer(a[i]);
                while(sum < 0) {
                    sum -= 2 * negative.poll();
                    cnt ++;
                }
            }
            System.out.println(cnt);
        }
    }
}

优先队列yyds