绿色通道

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1388 字

n题抄写耗时a_i，总时限t，求在t分钟内抄

一本通
练习

正文

/*
原题：T1603 「一本通 5.5 练习 2」绿色通道
题意：n 题抄写耗时 a_i，总时限 t，求在 t 分钟内抄完时最长连续空题段的最小可能长度。
思路：二分答案 L（最长空段）。判定时令 m=L+1，转化为“每 m 连续题中至少抄 1 题”，
     用单调队列 DP 求最少抄写耗时（同 T1602），若 ≤t 则可行。等价于 T1602 的对偶。
复杂度：时间 O(n·log n)，空间 O(n)。
易错点：L=0 表示全抄；L≥n 必然可行（可全空）；m=L+1，注意首窗、末窗边界处理。
*/
#include <bits/stdc++.h>
using namespace std;
// 给定 m，返回“每 m 连续题至少抄 1 题”约束下的最少抄写耗时；m>n 时允许全空返回 0
long long solve(const vector<long long>& a,int n,int m){
    if(m>n){
        return 0;
    }
    vector<long long> dp(n+1,LLONG_MAX);
    dp[0]=0;
    deque<int> q;
    q.push_back(0);
    for(int i=1;i<=n;i++){
        while(!q.empty()&&q.front()<i-m){
            q.pop_front();
        }
        dp[i]=a[i]+dp[q.front()];
        while(!q.empty()&&dp[q.back()]>=dp[i]){
            q.pop_back();
        }
        q.push_back(i);
    }
    long long ans=LLONG_MAX;
    int lo=max(1,n-m+1);
    for(int i=lo;i<=n;i++){
        ans=min(ans,dp[i]);
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long t;
    cin>>n>>t;
    vector<long long> a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int lo=0,hi=n,ans=n;
    while(lo<=hi){
        int mid=(lo+hi)/2;
        long long cost=solve(a,n,mid+1);
        if(cost<=t){
            ans=mid;
            hi=mid-1;
        }else{
            lo=mid+1;
        }
    }
    cout<<ans<<'\n';
    return 0;
}

绿色通道

正文

一本通·提高篇的其它内容