6 条题解
-
1
在这道题外面套个二分即可
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
- 上传者