ZOJ Bizarre Routine 2013杭州网赛B题

题目意思：

　　给定n, expect, a, b 要求你构造一组array[]，存放一个1..n的排列，使的下面的程序能输出YES

　　题目所示代码：

 bool less_than(x, y) {

     T++;

     return x < y;

 }

 void work(array[], l, r) {

     if (l >= r) return;

     swap(array[(l * A + r * B) / (A + B)], array[r]);

     int index = l;

     for (i = l; i < r; i++)

         if (less_than(array[i], array[r]))

             swap(array[index++], array[i]);

     swap(array[r], array[index]);

     work(array, l, index - );

     work(array, index + , r);

 }

 void main() {

     T = ;

     Input(n, expect, A, B, array[]);

     work(array, , n - );

     if (T == expect)

         Output("YES");

     else

         Output("NO");

 }

sort

　　壕无疑问这是一个快排！

n个数排列，T的上限是sigma(1..n-1) = n*(n-1)/2

而下限则可以通过递推得到

　　mi[x] = 0　　　　　　　　　　　　　　　　　　　　　　　　for x =0, 1

　　mi[x] = x-1 + min(mi[i] + mi[x-i-1]) (0 <=i < x)　　　　for x > 1

当然根据经验得到，i应该是取x/2的时候最好，跑了一下，mi数组也确实没变。。当然跑n^2的应该时间也够。

而且实际上 mi[i] + mi[x-i-1] 在i = 0..x/2呈现非递增的性质，解法用到了这个性质。

当expext在上下限之间的时候，可以通过递归构造

void work(int l, int r, int c)

构造区间[l,r] 使得这个区间的T = c

显然这个区间要消耗r - l次

设对这个区间的第一次排序后中间数在m位置，还要消耗区间[l,m - 1], [m+1, r]

当m = l .. (l+r)/2 (Ps: 当 m > (l+r)/2时和<= (l+r)/2的情况是等价的)

假如[l,m - 1], [m+1, r]均取最小值，则数值呈现非递减

假如[l,m - 1], [m+1, r]均取最大值，则数值呈现非递减

由于这个区间一定存在m符合条件，那么取第一个使得区间消耗最小值mi(l,m - 1) + mi(m+1, r) <= c - (r-l) 的必然符合要求(Ps: 把最小值和最大值在纸上画一下函数就明了)

让左区间取消耗最小值，然后递归构造

work(l,m-1,mi[l-m]) work(m1,r,c - (r-l) - mi[l-m])

我们希望区间[l, r]第一次sort后，p[l..r] = [ p[l..m-1], m ,p[m+1..r] ]

那么，通过给定的a, b计算得到m原本的下标，手动回滚他程序中的两次swap。

构造完毕，代码如下：

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int N = ;

 int a,b,p[N];

 int mi[N];

 inline bool can(int l,int r,int c){

     int n = r-l+;

     return c>=mi[n] && c<=n*(n-)/;

 }

 inline void mysort(int l,int m,int r,int id){

     p[m] = m;

     swap(p[m],p[r]);

     swap(p[r],p[id]);

 }

 void work(int l,int r,int c){

     if(l>r) return;

     if(l == r){

         p[l] = l;

         return;

     }

     int lt = l,rt = (l+r)/+, m;

     c -= r-l;

     while(lt<rt){

         m = (lt + rt)>>;

         if(mi[m-l]+mi[r-m] > c) lt = m + ;

         else rt = m;

     }

     m = lt;

     work(l,m-,mi[m-l]);

     work(m+,r,c-mi[m-l]);

     mysort(l,m,r,(l*a + r*b)/(a+b));

 }

 int n,m;

 int main(){

     //freopen("in.txt", "r", stdin);

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

         int x = i/, y = i-x-;

         mi[i] = mi[x]+mi[y]+i-;

     }

     //for(int i=0;i<=20;i++)cout<<i<<" "<<mi[i]<<endl;

     while(~scanf("%d%d%d%d",&n,&m,&a,&b)){

         if(!can(,n-,m)){

             puts("NOWAY");

             continue;

         }

         work(,n-,m);

         for(int i=;i<n;i++) printf(i==n-?"%d\n":"%d ",p[i]+);

     }

     return ;

 }

巴特西

ZOJ Bizarre Routine 2013杭州网赛B题

最新文章

热门文章