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;
    }
    
    • 1
      @ 2026-10-23 7:50:00

      逆天二分答案+线段树solution,不必多讲了。 两只log做法,只能说是唐完了。

      双log?没开玩笑吧。

      #include <bits/stdc++.h>
      #define int unsigned long long
      using namespace std;
      const int N = 1e5 + 5;
      int n, m, t[N], f[N][2], sum[N];
      struct tree {
      	int l, r;
      	int val;
      }tr[N << 2];
      void pushup(int u) {
      	tr[u].val = max(tr[u << 1].val, tr[u << 1 | 1].val);
      }
      void build(int u, int l, int r) {
      	tr[u].l = l, tr[u].r = r;
      	if(l == r) {
      		tr[u].val = -1;
      		return ;
      	}
      	int mid = (l + r) >> 1;
      	build(u << 1, l, mid);
      	build(u << 1 | 1, mid + 1, r);
      	pushup(u);
      }
      void update(int u, int p, int x) {
      	if(tr[u].l == tr[u].r) {
      		tr[u].val = x;
      		return ;
      	}
      	int mid = (tr[u].l + tr[u].r) >> 1;
      	if(p <= mid) update(u << 1, p, x);
      	else update(u << 1 | 1, p, x);
      	pushup(u);
      }
      long long query(int u, int l, int r) {
      	if(tr[u].l > r || tr[u].r < l || l > r) return -1;
      	if(tr[u].l >= l && tr[u].r <= r) {
      		return tr[u].val;
      	}
      	int mid = (tr[u].l + tr[u].r) >> 1;
      	if(r <= mid) return query(u << 1, l, r);
      	if(l > mid) return query(u << 1 | 1, l, r);
      	return max(query(u << 1, l, r), query(u << 1 | 1, l, r));
      }
      bool check(int mxx) {
      	memset(f, 0, sizeof(f));
      	int M = mxx;
      	build(1, 1, n);
      	for(int i=1; i<=M; ++i) {
      		f[i][0] = max(f[i - 1][0], f[i - 1][1]), f[i][1] = f[i - 1][1] + t[i];
      		update(1, i, f[i][0] - sum[i]);
      	}
      	for(int i=M+1; i<=n; ++i) {
      		f[i][0] = max(f[i - 1][0], f[i - 1][1]);
      		f[i][1] = query(1, i - M, i - 1) + sum[i]; 
      		update(1, i, f[i][0] - sum[i]);
      	}
      	int ans = max(f[n][0], f[n][1]);
      	if(sum[n] - ans <= m) return 1;
      	else return 0;
      }
      signed main() {
      	ios :: sync_with_stdio(0);
      	cin.tie(0), cout.tie(0);
      	cin >> n >> m;
      	for(int i=1; i<=n; ++i) {
      		cin >> t[i];
      		sum[i] = sum[i - 1] + t[i];
      	}
      	bool flag = 0;
      	for(int i=1; i<=n; ++i) {
      		if(t[i] <= m) flag = 1;
      	}
      	if(sum[n] <= m) {
      		cout << 0;
      		return 0;
      	}
      	if(!flag) {
      		cout << n;
      		return 0;
      	} 
      	int L = 0, R = n + 1;
      	while(L <= R) {
      		int mid = (L + R) >> 1;
      		if(check(mid)) {
      			R = mid - 1;
      		}
      		else {
      			L = mid + 1;
      		}
      	}
      	cout << L;
      	return 0;
      } 
      
      • 1
        @ 2025-6-24 14:36:39

        二分答案找间距x,在栽树过程中每(x+1)棵树就必须栽至少一棵,类比传球游戏,用单调队列优化dp。

        • 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;
          } 
          
          
          • 0
            @ 2026-10-23 8:19:10

            【一本通OJ 1603:绿色通道】

            • 0
              @ 2025-6-24 14:17:31

              直接二分答案然后dp去check

              线段树优化dp红红火火恍恍惚惚或或或或或或或或或或或或或或或或或

              时间复杂度 O(nlog2n)O(nlog^2n)

              #include<iostream>
              #include<cstring>
              #include<cstdio>
              #define N 50005
              #define int long long
              using namespace std;
              bool Test_MLE_start;
              int T=1,n,m,ans=0;
              int a[N],dp[N];
              struct tree{
              	int l,r,data;
              }t[N<<2];
              inline int reads(){
              	char c=getchar();
              	int sum=0,f=1;
              	while(!isdigit(c)){
              		if(c=='-') f=-1;
              		c=getchar();
              	}
              	while(isdigit(c)){
              		sum=(sum<<3)+(sum<<1)+(c^'0');
              		c=getchar();
              	}
              	return sum*f;
              }
              inline void files(){
              	freopen("E.in","r",stdin);
              //	freopen("std.out","w",stdout);
              }
              inline void clr(){
              //	Don't forget!
              
              }
              void pushup(int p){
              	int x=p<<1,y=p<<1|1;
              	t[p].data=min(t[x].data,t[y].data);
              }
              void builds(int p,int l,int r){
              	t[p].l=l,t[p].r=r;
              	if(l==r) return;
              	int mid=(l+r)>>1;
              	int x=p<<1,y=p<<1|1;
              	builds(x,l,mid),builds(y,mid+1,r);
              	pushup(p);
              }
              void changes(int p,int l,int r,int d){
              	if(l<=t[p].l&&t[p].r<=r){
              		t[p].data=d;
              		return;
              	}
              	int mid=(t[p].l+t[p].r)>>1;
              	int x=p<<1,y=p<<1|1;
              	if(l<=mid) changes(x,l,r,d);
              	if(r>mid) changes(y,l,r,d);
              	pushup(p);
              }
              int asks(int p,int l,int r){
              	if(l<=t[p].l&&t[p].r<=r) return t[p].data;
              	int mid=(t[p].l+t[p].r)>>1;
              	int x=p<<1,y=p<<1|1;
              	int ans=2e9;
              	if(l<=mid) ans=min(ans,asks(x,l,r));
              	if(r>mid) ans=min(ans,asks(y,l,r));
              	pushup(p);
              	return ans;
              }
              bool check(int k){
              	memset(dp,0,sizeof(dp));
              	builds(1,0,n+1);
              	for(int i=1;i<=n+1;i++){
              		int x=asks(1,max(0ll,i-k-1),i-1);
              		dp[i]=x+a[i];
              		changes(1,i,i,dp[i]);
              	}
              //	cout<<k<<":";
              //	for(int i=1;i<=n+1;i++) cout<<dp[i]<<" ";
              //	puts("");
              	return dp[n+1]<=m;
              }
              bool Test_MLE_end;
              signed main(){
              //	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
              //	files();
              //	T=reads();
              	while(T--){
              		clr();
              		n=reads(),m=reads();
              		for(int i=1;i<=n;i++) a[i]=reads();
              		int L=1,R=n;
              		while(L<=R){
              			int mid=(L+R)>>1;
              			if(check(mid)){
              				ans=mid;
              				R=mid-1;
              			}
              			else L=mid+1;
              		}
              		printf("%lld\n",ans);
              	}
              	return 0;
              }
              
              
              
              • @ 2025-6-24 14:19:24

                唐门 有 O(nlogn)O(nlogn) 的做法

            • 1

            信息

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