程序员人生 网站导航

BZOJ 3613 Heoi2014 南园满地堆轻絮 二分答案/线性做法

栏目:php教程时间:2015-04-08 08:31:00

题目大意:给定1个序列a,求1个单调不减的序列b,使max{|ai-bi|}最小


逗比题。。。。。


2分答案做法:

每次验证时从右向左扫描

如果当前数字小于等于右边的数字,就把这个数字向上调剂到极限(到达右边的数字或调剂的值到达上界)

如果当前数字大于右边的数字,就把这个数字向下调剂到与右边数字相等 没法如此做则返回false

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 5005005 using namespace std; int n,a[M]; long long Sa,Sb,Sc,Sd,mod; int F(int x) { long long re=Sd,temp=x; re+=Sc*temp%mod;(temp*=x)%=mod; re+=Sb*temp%mod;(temp*=x)%=mod; re+=Sa*temp%mod; return int(re%mod); } bool Judge(int x) { int i,min_num=2147483647; for(i=n;i;i--) { if(a[i]<=min_num) min_num=min(min_num,a[i]+x); else if(a[i]-min_num>x) return false; } return true; } int Bisection() { int l=0,r=mod⑴; while(l+1<r) { int mid=l+r>>1; if( Judge(mid) ) r=mid; else l=mid; } return Judge(l)?l:r; } int main() { int i; cin>>n>>Sa>>Sb>>Sc>>Sd>>a[1]>>mod; for(i=2;i<=n;i++) a[i]=(F(a[i⑴])+F(a[i⑵]))%mod; cout<<Bisection()<<endl; return 0; }

但是500W明显nlogn压力山东大学(虽然我本机慢的要死最大的点都只跑了1.5秒)

因此我还是去看了标程的线性做法

打开cpp的那1刻我震精了――


答案等于差值最大的逆序对的差值+1>>1

正确性明显。。。。。。明显。。。。。明显。。。。。。。。。


#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 5005005 using namespace std; int n,ans,a[M]; long long Sa,Sb,Sc,Sd,mod; int F(int x) { long long re=Sd,temp=x; re+=Sc*temp%mod;(temp*=x)%=mod; re+=Sb*temp%mod;(temp*=x)%=mod; re+=Sa*temp%mod; return int(re%mod); } int main() { int i; cin>>n>>Sa>>Sb>>Sc>>Sd>>a[1]>>mod; for(i=2;i<=n;i++) a[i]=(F(a[i⑴])+F(a[i⑵]))%mod; int max_val=0; for(i=1;i<=n;i++) { max_val=max(max_val,a[i]); ans=max(ans,max_val-a[i]+1>>1); } cout<<ans<<endl; return 0; }


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐