牛客小白月赛96 B~C

B-最少操作次数

有一个长度为的字符串，仅包含和两种字符。 每次可以选择两个索引i和，并满足以下条件之一： 1.如果区间 中 的数量大于 的数量，可以把此区间的所有数字都变成 。

2.如果区间 中 的数量大于 的数量，可以把此区间的所有数字都变成 。

把整个串变成全 或者全 的最少操作次数，如果无解，输出。

分类讨论、贪心

当，显然答案为。

当，两个字母相同答案为，反之为。

当，要操作次数最少，每次操作越多数越好。当序列中数量与数量相同时则需要操作两次。不同时只需次操作即可。若其中一个数量为答案为。

import java.io.*;
import java.util.*;
public class Main {
    static Scanner sc = new Scanner(System.in);
    static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        String s = sc.next();
        if(n == 1){
            pw.println(0);
        }else if(n == 2){
            if(s.charAt(0) == s.charAt(1)) pw.println(0);
            else pw.print(-1);
        }else{
            int a = 0, b  = 0;
            for(int i = 0; i < n; i ++){
                if(s.charAt(i) == '1') a ++;
                else b ++;
            }
            if(a == 0 || b == 0) pw.print(0);
            else if(a == b) pw.print(2);
            else pw.print(1);
        }
        pw.flush();
        pw.close(); 
    }
}

C-最多数组数量)

一个山峰数组定义为由三个元素组成,满足 且 。

有一个长度为 的数组 ，他将选择两个索引 ,然后分成三个非空连续的子数组，即，满足是一个山峰数组。

共有多少个不同的 可以满足条件.

前缀和+二分

枚举第一个区间的右端点，二分查找满足山峰数组的第二个区间的最小右端点（若存在），累加所有。

所有的区间和用前缀和数组计算。

import java.io.*;
import java.util.*;
public class Main {
    static Scanner sc = new Scanner(System.in);
    static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static int n;
    static long ans = 0, a[], s[];
    public static void main(String[] args) throws Exception {
        n = sc.nextInt();
        a = new long[n + 1];
        s = new long[n + 1];
        for(int i = 1; i <= n; i ++){
            a[i] = sc.nextInt();
            s[i] = s[i - 1] + a[i];
        }
        for(int i = 1; i <=n - 2; i ++){
            long lsum = s[i];
            int l = i + 1, r = n - 1, idx = -1;
            while(l <= r){
                int m = (l + r) >>> 1;
                if(s[m] - s[i] > lsum && s[m] - s[i] > s[n] - s[m]){
                    idx = m;
                    r = m - 1;
                }else{
                    l = m + 1;
                }
            }
            if(idx != -1) ans += n - 1 - idx + 1;
        }
        pw.println(ans);
        pw.flush();
        pw.close(); 
    }

}