题解：CF1923D（Slimes）

题解：CF1923D（Slimes）

一、 理解题意

CF链接
洛谷链接

二、 设计算法

我们不难想到，为了让当前史莱姆用最短的时间被吃掉，我们一定要让他左侧或右侧的连续一段合并成一个很大的史莱姆，再让这个很大的史莱姆吃掉当前史莱姆。于是，最终的答案统计被分为两类：左侧合并和右侧合并。
怎样知道一段区间内的史莱姆合并完之后能否吃掉当前史莱姆呢？我们可以维护所有史莱姆的体积的前缀和与后缀和，在计算答案时，二分分别找出离当前史莱姆最近、在他左/右侧的史莱姆，使得找到的史莱姆到当前史莱姆之间（不包括当前史莱姆）所有史莱姆的体积加起来严格大于当前史莱姆的体积。最终的答案显然是当前史莱姆与二分出的史莱姆的编号之差的绝对值。两种情况求最小值即可。
但是问题又来了：如果一段区间内所有的史莱姆的体积都相等，那么他们就不可能合并。因此，我们还要维护出在某个史莱姆前/后面多少个史莱姆才能找到一个和他本身体积不同的。这样，我们在二分出答案后，分别和对应的至少要有的长度取最大值。（左侧的情况，就是“前面有多少个”，右侧反之）
那么问题就解决了吗？并没有！我们完美忽略了一种情况：当前史莱姆旁边的好兄弟体积够大，能够直接吃掉当前史莱姆，此时答案为 $1$。

三、 计算代价

维护一堆量、遍历每个史莱姆：$O(n)$；
求答案时二分：$O(log(n))$；
总共：$O(n\cdot log(n))$。

四、 实现代码

#include<bits/stdc++.h>
#define N 330000
using namespace std;
int a[N]={},n=0,t=0;
long long sh[N]={},sq[N]={};
int lst[N]={},nxt[N]={};
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		sh[n+1]=0;
		sq[0]=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		for(int i=1;i<=n;i++){
			sq[i]=sq[i-1]+a[i];
			if(i!=1&&a[i]==a[i-1]){
				lst[i]=lst[i-1]+1;
			}else{
				lst[i]=1;
			}
		}
		for(int i=n;i>=1;i--){
			sh[i]=sh[i+1]+a[i];
			if(i!=n&&a[i]==a[i+1]){
				nxt[i]=nxt[i+1]+1;
			}else{
				nxt[i]=1;
			}
		}
		for(int i=1;i<=n;i++){
			if(i>1&&a[i-1]>a[i]||i<n&&a[i+1]>a[i]){
				printf("1 ");
				continue;
			}
			int ret=1<<30;
			int l1=0,r1=i;
			while(l1+1<r1){
				int mid=(l1+r1)/2;
				if(sq[i-1]-sq[mid-1]>a[i]){
					l1=mid;
				}else{
					r1=mid;
				}
			}
			if(l1!=0&&lst[i-1]!=i-1){
				ret=min(ret,max(lst[i-1]+1,i-l1));
			}
			int l2=i,r2=n+1;
			while(l2+1<r2){
				int mid=(l2+r2)/2;
				if(sh[i+1]-sh[mid+1]<=a[i]){
					l2=mid;
				}else{
					r2=mid;
				}
			}
			if(r2!=n+1&&nxt[i+1]!=n-i){
				ret=min(ret,max(nxt[i+1]+1,r2-i));
			}
			if(ret==1<<30){
				ret=-1;
			}
			printf("%d ",ret);
		}
		printf("\n");
	}
	return 0;
}