UER#7 T2

题意:给定n个数，对于2到n，分别输出一个答案。答案定义为：对于当前的数k，在原数组中找一个长度为k的区间，使得区间最值之差最小，输出差值。注意，差值允许5%的误差。

很少看见近似算法的题啊。。跪烂VFK大爷。

首先可以注意到的是，答案一定是单增的。我们再发现，随着1.05指数不断增加，之后肯定会有质的飞跃（毕竟是指数函数），也就是说，到时候一定有一大段区间的答案都是同一个数。所以我们只要分别找出每一个段的答案就好了。段数大概是log的（不会证，凭感觉吧。。。

先把2和n的答案计算出来，然后分治下去。如果当前分治的区间，左端点的答案误差范围已经和右边答案的误差范围相交，说明夹在他们中间的数们答案全一样，随便选一个复制给他们就好了。

时间复杂度O（nlogn）。跪烂。。

 #include<bits/stdc++.h>

 using namespace std;

 #define N 100005

 #define INF 1e9

 #define eps 1e-5

 inline int read(){

     int x=,f=; char a=getchar();

     while(a<'' || a>'') {if(a=='-') f=-; a=getchar();}

     while(a>='' && a<='') x=x*+a-'',a=getchar();

     return x*f;

 }

 int n,mx[N][],mn[N][],ans[N],Log[N];

 inline int Max(int x){

     return (int)((double)x*1.05+eps);

 }

 inline int Min(int x){

     return (int)((double)x*0.95+-eps);

 }

 inline void pre(){

     Log[]=-; for(int i=;i<=n;i++) Log[i]=Log[i>>]+;

     for(int i=;i<=;i++)

         for(int j=;j<=n;j++){

             mx[j][i]=max(mx[j][i-],mx[min(n,j+(<<(i-)))][i-]);

             mn[j][i]=min(mn[j][i-],mn[min(n,j+(<<(i-)))][i-]);

         }

 }

 inline int qmx(int l,int r){

     return max(mx[l][Log[r-l+]],mx[r-(<<Log[r-l+])+][Log[r-l+]]);

 }

 inline int qmn(int l,int r){

     return min(mn[l][Log[r-l+]],mn[r-(<<Log[r-l+])+][Log[r-l+]]);

 }

 inline void cal(int x){

     ans[x]=INF;

     for(int i=;i<=n-x+;i++) ans[x]=min(ans[x],qmx(i,i+x-)-qmn(i,i+x-));

 }

 void dc(int l,int r){

     if(r-l<=) return;

     if(Max(ans[l])>=Min(ans[r])){

         int tmp=Max(ans[l]);

         for(int i=l+;i<r;i++) ans[i]=tmp;

         return;

     }

     int mid=(l+r)>>;

     cal(mid);

     dc(l,mid); dc(mid,r);

 }

 int main(){

     n=read(); for(int i=;i<=n;i++) mx[i][]=mn[i][]=read();

     pre();

     cal(); cal(n); dc(,n);

     for(int i=;i<=n;i++) printf("%d\n",ans[i]);

     return ;

 }

巴特西

UER#7 T2

最新文章

热门文章