题目地址

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll anss=1e18,n,m,k,flag,x[300001],h[300001];
void ans2(){//处理当x[i]均为1的情况 
	ll an = 0,o = m/k+1,p = m%k,q = 0,l = h[n];
	while(h[n] > 0){
		h[n] -= o;
		an++;
		if(!q&&an >= p){
			q = 1;
			o--;
		}
	}
	cout << l - an;
}
/*
6 9 4
1 1 4 5 1 4
//
27 40 3
1 1 1 3 5 2 3 3 1 5 3 3 1 3 3 2 5 5 2 4 4 3 4 1 2 3 5 
*/
bool judge(int s){//判断 
	map<ll,ll> y;
	ll start = 1,end = 1,le = 0,anp = 0,an = 0,op = 0;
	for(int i = 1; i <= n; i++){
		if(x[i] > s)	return 0;//单个单位 > 上限
		while(an + x[i] > s){//当前区间和 > 上限 
//cout << "&" << y[start] <<" " <<an <<"|";
			an -= y[start];//left后移 
//	||		le++;
			start++;
			end++;//right后移 
		}
		end++;//right后移 
		y[end] = x[i];//落位 
		an += x[i];
//cout <<"@ " <<start << " " <<end <<" @";
		if(start > end)	return 0;//防超界 
		if(end - start > k){//当区间 > k 
//cout << 2;
			an -= y[start];//left后移 
			start++;
		}
		if(end > m){
//cout <<end<<"eff";
			return 0;
		}
		anp = max(anp,an);
	}
	if(end > m)	return 0;
//cout <<"asd" << s << " " << end <<endl;
	anss = min(anss,anp);
	return 1;
}
void ans3(){//二分答案 
	ll mid,l = 0,r = h[n];
	while(l <= r){
		mid = (r+l)/2;
//cout << l << " " << mid << " " << r <<endl<<endl;
		if(!judge(mid))	l = mid+1;
		else	r = mid-1;
	}
	cout << h[n] - l;
}
void ans(int id){
	ll an = 0;
	for(int i = 1; i <= n; i++)	h[i] = h[i-1] + x[i];//前缀和 
	if(id == 2){
		ans2();
		return ;
	}
	if(id == 3){
		ans3();
		return ;
	}
	
	for(int i = 0; i <= n-k; i++)	an = max(an,h[k+i] - h[i]);//m=n的情况 
	cout << h[n] - an;
	return ;
}
int main(){
	freopen("nut.in","r",stdin);
	freopen("nut.out","w",stdout);
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++){
		cin >> x[i];
		if(x[i] == 1)	flag++;
	}
	if(n == m){
		ans(1);
		return 0;
	}
	if(flag == n){
		ans(2);
		return 0;
	}
	ans(3);
	return 0;
}