6 条题解

  • 0
    @ 2026-10-23 8:36:28

    lzm的线段树太招了,考试谁跟你写线段树,难写易错复杂度还高,当然是要用二分答案+DP来做咯,首先二分间距,如果可行就二分找更小,否则找更大,DP就是O(NM)线性DP(还是算背包?)再加一个单调队列优化就可,最后输出二分的答案 时间复杂度O(nlogn)

    代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    void lhhsyn(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    }
    int n,m;
    int t[50005],f[50005];
    bool check(int x){
    	deque<int> q;
    	for(int i=1;i<=n+1;i++){
    		f[i]=1e9;
    	}
    	f[0]=0;
    	q.push_back(0);
    	for(int i=1;i<=n+1;i++){
    		while(!q.empty()&&q.front()<i-x-1)q.pop_front();
    		f[i]=min(f[i],f[q.front()]+t[i]);
    		while(!q.empty()&&f[q.back()]>=f[i])q.pop_back();
    		q.push_back(i);
    	}
    	if(f[n+1]<=m)return 1;
    	else return 0;
    }
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		cin>>t[i];
    	}
    	int l=0,r=n,ans;
    	while(l<=r){
    		int mid=(l+r)/2;
    		if(check(mid)){
    			r=mid-1;
    			ans=mid;
    		}
    		else l=mid+1;
    	}
    	cout<<ans;
    	return 0;
    } 
    
    

    信息

    ID
    288
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    77
    已通过
    20
    上传者