6 条题解
-
0
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
- 上传者