首页 > 代码库 > BZOJ 4582: [Usaco2016 Open]Diamond Collector
BZOJ 4582: [Usaco2016 Open]Diamond Collector
Descrirption
给你一个长度为 \(n\) 的序列,求将它分成两个序列后最多个数,每个序列最大值最小值不能超过 \(k\)
Sol
二分+DP.
排一下序,找出以这个点结尾和开始的位置.
这个玩意可以二分也可以用单调队列,随便搞啊...
然后统计答案就是枚举第二个序列的起点,然后往后扫的时候统计一下,第一个序列的最大长度就可以了.
Code
/************************************************************** Problem: 4582 User: BeiYu Language: C++ Result: Accepted Time:76 ms Memory:1876 kb****************************************************************/ #include <cstdio>#include <algorithm>#include <iostream>using namespace std; const int N =50050; int n,k,ans;int a[N];int f[N],g[N]; inline int in(int x=0){ scanf("%d",&x);return x; }int uppp(int x){// >= int l=1,r=n,mid; for(;l<=r;){ mid=(l+r)>>1; if(a[mid] < x) l=mid+1; else r=mid-1; }return l;}int lwww(int x){//<= int l=1,r=n,mid; for(;l<=r;){ mid=(l+r)>>1; if(a[mid] <= x) l=mid+1; else r=mid-1; }return r;}int main(){ n=in(),k=in(); for(int i=1;i<=n;i++) a[i]=in(); sort(a+1,a+n+1); for(int i=1;i<=n;i++){ f[i]=i-uppp(a[i]-k)+1; g[i]=lwww(a[i]+k)-i+1; } // for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;// for(int i=1;i<=n;i++) cout<<f[i]<<" ";cout<<endl;// for(int i=1;i<=n;i++) cout<<g[i]<<" ";cout<<endl; for(int i=1;i<=n;i++){ ans=max(ans,f[i-1]+g[i]); f[i]=max(f[i],f[i-1]); } cout<<ans<<endl; return 0;}
BZOJ 4582: [Usaco2016 Open]Diamond Collector
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。