好排列 题解

· · 题解

[B] 好排列 题解

测试点 1 \sim 5

直接模拟操作过程即可。对每个数，我们考虑其位置，并用 O(n) 的复杂度计算 f_0(x),f_1(x),g_0(x),g_1(x)。

时间复杂度：O(n^2 k)。

测试点 6 \sim 9, 18 \sim 19

发现可以通过前缀和与后缀和优化枚举过程，因此可以在每次考虑位置前计算好每个 f_0(x),f_1(x),g_0(x),g_1(x)。

时间复杂度：O(nk)。

测试点 10 \sim 17, 20 \sim 25

下面将 A_i=0 表述为“空位”，A_i \ne 0 表述为“被占用”。

首先，一个数字只会选择一段连续的空位中的中间位置（靠两边的一定更劣）。特别地，如果连续空位长度 \le 2，则需要统计两侧有多少个被占用的位置。

注意到一个数字进入某个位置将断开一个连续空位段，同时可能影响至多两个相邻的空位段。

考虑维护一个链表处理哪些段相邻，再用一个堆维护哪个段最优。这个堆每次需要更新其中至多两个元素，需要手写。注意每更新一个元素就要更新一次堆，否则堆的性质会被破坏。

也可以考虑用 set 维护，不过常数较大，不推荐。

时间复杂度：O(k \log n)。

正解代码：

#include <iostream>
#include <memory.h>
using namespace std;

inline void train() {
       ios::sync_with_stdio(false);
       cin.tie(0);
       cout.tie(0);
}

constexpr int N = 1e6+3;

inline int maxi(int a, int b) {
    return a > b ? a : b; 
}

inline int mini(int a, int b) {
    return a < b ? a : b;
}

int nextfree[N], prevfree[N];   
bool occupied[N];

inline int right_dis(int pos) {
    return nextfree[pos] - pos - 1;
}

inline int left_dis(int pos) {
    return pos - prevfree[pos] - 1;
}

struct range {
    int l, r;
    bool ok = false;
    range() {
    }
    range(int l, int r) : l(l), r(r), ok(true) {
    }
    int len() const {
        return r-l+1;
    }
    int dis() const {
        if (len() > 2) return 0;
        else if (len() == 1) return left_dis(l) + right_dis(l);
        else return mini(left_dis(l), right_dis(r));
    }
    int pos() const {
        if (len() > 2) return (l+r)/2;
        else if (len() == 1) return l;
        else {
            if (left_dis(l) <= right_dis(r)) return l;
            else return r;
        } 
    }
};
range heap[N];
int lat[N], rat[N];
int heaprear = 1;

inline void clear() {
    heaprear = 1;
    memset(lat, -1, sizeof(lat));
    memset(rat, -1, sizeof(rat));
    memset(occupied, 0, sizeof(occupied));
    memset(heap, 0, sizeof(heap));
}

bool operator < (const range &a, const range &b) {
    if (!a.ok) return false;
    else if (!b.ok) return true;
        // 中间位置上至少有一边有人
    if (a.len() <= 2 && b.len() <= 2) {
        int maxa = a.dis(), maxb = b.dis();
        if (maxa == maxb) {
            return a.l < b.l;
        }
        return maxa < maxb;
    }
    int adiv = a.len() / 2 + (a.len() % 2), bdiv = b.len() / 2 + (b.len() % 2);
    if (adiv == bdiv) return a.l < b.l;
    return adiv > bdiv;
    //return a.len() > b.len();
}

inline void swaps(range &a, range &b) {
    static range tmp;   // or range;
    tmp = a;
    a = b;
    b = tmp;
}

inline void swaps(int &a, int &b) {
    static int tmp;
    tmp = a;
    a = b;
    b = tmp;
}

void adjust(int pos) {
    if (pos < 1) return;
    auto &self = heap[pos];
    auto &father = heap[pos>>1];
    auto &lc = heap[pos<<1];
    auto &rc = heap[(pos<<1)|1];
    if (pos > 1 && heap[pos] < father) {
        lat[self.l] = pos>>1;
        rat[self.r] = pos>>1;
        lat[father.l] = pos;
        rat[father.r] = pos;
        swaps(father, self);    // Move father to here and here to father
        adjust(pos>>1);
    } else if ((pos<<1) < heaprear) {
        if (lc < self && lc.ok) {
            if (rc < lc) {
                lat[self.l] = (pos << 1) | 1;
                rat[self.r] = (pos << 1) | 1;
                lat[rc.l] = pos;
                rat[rc.r] = pos;
                swaps(rc, self);
                adjust((pos << 1) | 1);
            }
            else {
                lat[self.l] = pos << 1;
                rat[self.r] = pos << 1;
                lat[lc.l] = pos;
                rat[lc.r] = pos;
                swaps(lc, self);
                adjust(pos << 1);
            }
        } else if (rc < self && rc.ok) {
            lat[self.l] = (pos<<1)|1;
            rat[self.r] = (pos<<1)|1;
            lat[rc.l] = pos;
            rat[rc.r] = pos;
            swaps(rc, self);
            adjust((pos<<1)|1); 
        }
    }
}

inline void occupy(int pos) {
    occupied[pos] = true;
    prevfree[nextfree[pos]] = prevfree[pos];    // To calculate the dsitance to know
    adjust(lat[nextfree[pos]]);
    nextfree[prevfree[pos]] = nextfree[pos];
    adjust(rat[prevfree[pos]]);
}

void pushin(range object) {
    if (object.len() <= 0) return;
    object.ok = true;
    lat[object.l] = heaprear;
    rat[object.r] = heaprear;
    heap[heaprear] = object;
    heaprear++;
    adjust(heaprear - 1);
}

range popout() {
    range result = heap[1];
    heap[1].ok = false;
    lat[heap[1].l] = -1;
    rat[heap[1].r] = -1;
    swaps(heap[heaprear - 1], heap[1]);
    heaprear--;
    lat[heap[1].l] = (1 <= heaprear) ? -1 : 1;
    rat[heap[1].r] = (1 <= heaprear) ? -1 : 1;
    adjust(1);
    return result;
}

inline void execute() {

    int n,k;
    cin>>n>>k;

    if (k <= 2) {
        if (k == 1) cout<<"1";
        else cout<<n;
        cout<<endl;
        return;
    }
    k-=2;

    for (int i = 2; i <= n-1; i++) {
        nextfree[i] = (i == n-1) ? n+1 : (i+1);
        prevfree[i] = (i == 2) ? 0 : (i-1);
    }
    occupied[1] = occupied[n] = true;
    pushin(range(2, n-1));
    for (int step = 1; step < k; step++) {
        range cur = popout();
        int cp = cur.pos();
        occupy(cp);
        if (cur.len() > 1) {
            pushin(range(cur.l, cp-1));
            pushin(range(cp+1, cur.r));
        }
    }
    range cur = popout();
    int cp = cur.pos();
    cout<<cp<<endl;

    //cout<<flush;

//  return 0;
}

int main() {
    train();
    int t;
    cin>>t;
    for (int _ = 0; _ < t; _++) {
        clear();
        execute();
    }
    return 0;
}

另外，本题有一些神秘的部分分，没有细讲是因为出题人不会或不想写。