BZOJ 3613 Heoi2014 南園滿地堆輕絮 二分答案/線性做法
來源：程序員人生 發布時間：2015-04-08 08:31:00 閱讀次數：4050次
題目大意：給定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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
