题目

---

• 这道题的思路很暴力，通过优化的枚举就可以得到一个很不错的时间复杂度，只是坑点有点多，所有坑点我都会在接下来的文字中叙述。

• 前置芝士：二分答案(不会的先去学)。

• 第一种，暴力枚举 (最高54分)

• 我们可以将每一个数元素所对应的 $K$ 从最大值开始向前枚举，这种算法可以得到较高的分数，但肯定不是正解，但如果思路错了分数甚至没有暴力高。

#include<bits/stdc++.h>
using namespace std;
long long n,s,x,sum[100005];
bool work(int i,int mid){
	if((sum[i+mid-1]-sum[i-1]>s)||(sum[i+mid*2-1]-sum[i+mid-1]>s))
		return false;
	return true;
}
int main(){
	scanf("%d%d",&n,&s);
	for(int i=1;i<=n;++i){
		scanf("%d",&x);
		sum[i]=sum[i-1]+x;
	}
	for(int i=1;i<=n;++i){
		int ans=0;
		for(int j=(n-i+1)/2;j>=1;j--) 
			if(work(i,j)){
				ans=j;break;
			}
		printf("%d\n",ans*2);
	}
	return 0;
} 

• 第二种，二分答案优化(其实也是暴力)(120分)
• 我们很容易发现，每一个序列的前 $K$ 个元素之和随 $K$ 的减小而减小，是单调的。因此可以将满足“当前 $K$ 个元素的和小于 $S$ ”的 $K$ 的范围通过二分求出。

  int l=0,r=(n-i+1)/2/*小细节*/t=0;
  while(l<=r){//万能的二分答案板子 
      int mid=l+r>>1;
      if(sum[i+mid-1]-sum[i-1]>s)
          r=mid-1;
      else{
          l=mid+1;
          t=mid;	
      }
  }

• $K$ 满足的第一个取值范围即为 $0≤K≤t$。
• 但是后 $K$ 个元素之和关于 $K$ 单调吗？其实不是的，这是个坑点(当时卡这里卡了一个晚自习)。
• 这里给出一组数据：1 2 2 9 5 1 1 1

1. 当 $i=1$，$K=4$时，后 $K$ 个元素之和为8；
2. 当 $i=1$，$K=3$时，后 $K$ 个元素之和为15；
3. 当 $i=1$，$K=2$时，后 $K$ 个元素之和为11。

• 我们发现，后 $K$ 个元素之和关于 $K$ 并不单调，因此不能将后 $K$ 个元素带入二分求出范围！
• 因此我们求出 $K$ 的第一个范围之后，需要用其他方法求出满足第二个条件的 $K$ 的最值，我直接使用第一种暴力枚举的方法，然后惊奇的发现过了，时间也很短，不知道是不是这题数据太水。

AC code

#include<bits/stdc++.h>
using namespace std;
int n,s,x,sum[100005];
int main(){
	scanf("%d%d",&n,&s);
	for(int i=1;i<=n;++i){
		scanf("%d",&x);
		sum[i]=sum[i-1]+x//前缀和优化;
	}
	for(int i=1;i<=n;++i){
		int l=0,r=(n-i+1)/2,ans=0,t=0;
		while(l<=r){ 
			int mid=l+r>>1;
			if(sum[i+mid-1]-sum[i-1]>s)
				r=mid-1;
			else{
				l=mid+1;
				t=mid;	
			}
		}
		for(int j=t;j>=1;j--)//从后向前枚举 
			if(sum[i+j*2-1]-sum[i+j-1]<=s){
				ans=j;break;
			}
		printf("%d\n",ans*2);
	}
	return 0;
}  

• 如果评论区有大佬有更好的算法欢迎指出^^。