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代码

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 \in [1,n)\)，有 \(s_1+s_2+...+s_n=s_i+s_{i+1}\)。若不可构造，输出 \(NO\)，否则输出 \(YES\)，以及所构造的数组。

思路

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

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

时间复杂度：\(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();
            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 \in [1,n]\)）中的最小值。

思路

对于题给式子 \(a_1+a_2+...+a_k \geq a_1+a_2+...+a_m\)，

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

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

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

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

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

时间复杂度：\(O(n \log 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();
            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