6 条题解

  • 1
    @ 2026-10-23 8:32:30

    在这道题外面套个二分即可

    code:

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N=1e6+5;
    int n,m,t[N],sum;
    struct node{
    	int x,id;
    };
    bool operator < (node a,node b){
    	return a.x>b.x;
    }
    node makenode(int x,int y){
    	node z;
    	z.x=x; z.id=y;
    	return z;
    }
    bool check(int mid){
    	priority_queue<node> pq;
    	pq.push(makenode(0,0));
    	for(int i=1;i<=n;i++){
    		node x=pq.top();
    		while(i-x.id>mid+1){
    			pq.pop();
    			x=pq.top();
    		}
    		pq.push(makenode(t[i]+x.x,i));
    	}
    	node x=pq.top();
    	while(n-x.id>mid){
    		pq.pop();
    		x=pq.top();
    	}
    	if(x.x<=m) return 1;
    	return 0;
    }
    signed main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++) cin>>t[i];
    	int l=0,r=n;
    	while(l<r-1){
    		int mid=((l+r)>>1);
    		if(check(mid)==0) l=mid;
    		else r=mid;
    	}
    	if(check(r)) cout<<r;
    	else cout<<l;
    	return 0;
    }
    

    信息

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