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; } -
1
逆天二分答案+线段树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; } -
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; } -
0
直接二分答案然后dp去check
线段树优化dp红红火火恍恍惚惚或或或或或或或或或或或或或或或或或
时间复杂度
#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; }
- 1
信息
- ID
- 288
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 77
- 已通过
- 20
- 上传者