本文主要是介绍Educational Codeforces Round 162 (Rated for Div. 2) -- D Slimes -- 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
D Slimes -- 题解
题目大意：
思路解析：
对于每个史莱姆来说，他要么被左边区间合并出来的史莱姆合并，要么被右边区间合并出来的史莱姆合并。解决这个问题我们只需要查询左边那个区间是大于他的，右边那个区间是大于他的，可以前缀和+二分搜索来解决这个问题。
但是如果我们找到一个区间 2 2 2 2 > 7 ,但是他显然不能被这个区间合并，因为相同的史莱姆不能合并，即这个区间无法合并成一个大史莱姆，可以发现如果一个区间只要出现不想等的数字，那么一定能合并为一个大史莱姆。 （这个信息也可以用前缀和+二分维护）
所以第一次往左边搜索，第二次往右边搜索。
代码实现：
import java.io.*;
import java.util.*;public class Main {static int inf = (int) 1e9;static int mod = (int) 1e9 + 7;static int mod9 = 998244353;static Vector<Integer>[] g;static char[] s;static char[] a;public static void main(String[] args) throws IOException {int T = input.nextInt();for (int o = 0; o < T; o++) {int n = input.nextInt();int[] arr = new int[n+1];long[] sum1 = new long[n+2];long[] sum2 = new long[n+2];int[] res = new int[n+1];for (int i = 1; i <= n; i++) {res[i] = n+1;arr[i] = input.nextInt();}arr[0] = arr[1];for (int i = 1; i <= n; i++) {sum1[i] = sum1[i-1] + arr[i];sum2[i] = sum2[i - 1] + (arr[i] != arr[i-1] ? 1 : 0);}for (int i = 1; i <= n; i++) {int ans = -1;int l = 1;int r = i - 1;// i - midwhile (l <= r){int mid = (l + r) >> 1;if (sum1[i-1] - sum1[mid-1] > arr[i] && ((sum2[i-1] - sum2[mid] >= 1 || arr[i-1] > arr[i]) || i - 1 == mid)){ans = mid;l = mid + 1;}else {r = mid - 1;}}if (ans != -1) res[i] = Math.min(res[i], i - ans);}for (int i = n; i >= 1; i--) {if (i == n){sum2[i] = 0;sum1[i] = arr[i];}else {sum1[i] = sum1[i+1] + arr[i];sum2[i] = sum2[i + 1] + (arr[i] != arr[i+1] ? 1 : 0);}}for (int i = 1; i <= n; i++) {int ans = -1;int l = i+1;int r = n;// i - midwhile (l <= r){int mid = (l + r) >> 1;if (sum1[i+1] - sum1[mid+1] > arr[i] && ((sum2[i+1] - sum2[mid] >= 1||arr[i+1] > arr[i]) || mid -1 == i)){ans = mid;r = mid - 1;}else {l = mid + 1;}}if (ans != -1) res[i] = Math.min(res[i], ans - i);}for (int i = 1; i <= n; i++) {if (res[i] == n+1) out.print(-1 + " ");else out.print(res[i] + " ");}out.println();}out.flush();out.close();br.close();}static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static Input input = new Input(System.in);static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static class Input {public BufferedReader reader;public StringTokenizer tokenizer;public Input(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = null;}public String next() {while (tokenizer == null || !tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public char[] nextChars(){return next().toCharArray();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}}
}这篇关于Educational Codeforces Round 162 (Rated for Div. 2) -- D Slimes -- 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
