算法设计基础（六）

第 $k$ 大数，逆序对，中位数等，都是经典问题

中位数

Acwing105

const int maxn = 100000 + 10;
ll row[maxn], col[maxn], sum[maxn];
int N, M, T;

void init() {
    memset(row, 0, sizeof row);
    memset(col, 0, sizeof col);
}

inline ll calc(ll *A, int n) {
    memset(sum, 0, sizeof sum);

    // prework
    _rep(i, 1, n) A[i] -= A[0] / (1ll * n);
    _rep(i, 1, n) sum[i] = sum[i-1] + A[i];

    // mid
    sort(sum+1, sum+1+n);
    ll ans = 0;
    _rep(i, 1, n) ans += abs(sum[i] - sum[(1+n)>>1]);
    return ans;
}

void solve() {
    if (row[0] % N == 0 && col[0] % M == 0) {
        ll ans1 = calc(row, N), ans2 = calc(col, M);
        printf("both %lld\n", ans1 + ans2);
    }
    else if (row[0] % N == 0) {
        ll ans = calc(row, N);
        printf("row %lld\n", ans);
    }
    else if (col[0] % M == 0) {
        ll ans = calc(col, M);
        printf("column %lld\n", ans);
    }
    else puts("impossible");
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d%d", &N, &M, &T);

    // get data
    while (T--) {
        int x, y;
        scanf("%d%d", &x, &y);
        row[x]++, col[y]++;
    }

    // prework
    _rep(i, 1, N) row[0] += row[i];
    _rep(i, 1, M) col[0] += col[i];

    // then solve
    solve();
}

对顶堆

对顶堆求解动态中位数问题非常常见

Acwing106

// tot m numbers
int n, m, T;

void init() {
    //
}

void solve() {
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int> > minHeap;

    //debug(m);
    int cnt = 0;
    _rep(i, 1, m) {
        int x;
        scanf("%d", &x);
        //debug(x)

        if (maxHeap.empty() || x <= maxHeap.top()) maxHeap.push(x);
        else minHeap.push(x);

        if (maxHeap.size() > minHeap.size() + 1) minHeap.push(maxHeap.top()), maxHeap.pop();
        if (minHeap.size() > maxHeap.size()) maxHeap.push(minHeap.top()), minHeap.pop();

        if (i & 1) {
            cnt++;
            printf("%d ", maxHeap.top());

            if (cnt % 10 == 0) printf("\n");
        }
    }
    if (cnt % 10) printf("\n");
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> T;

    while (T--) {
        init();

        // get data
        scanf("%d%d", &n, &m);
        printf("%d %d\n", n, (m+1)/2);

        // then solve
        solve();
    }
}

逆序对

Acwing107

const int maxn = 500000 + 10;
int n, a[maxn], b[maxn];
ll ans = 0;

void init() {
    ans = 0;
}

void merge(int l, int mid, int r) {
    if (l == r) return;
    if (l + 1 == r) {
        if (a[l] > a[r]) swap(a[l], a[r]), ans++;
        return;
    }

    merge(l, (l+mid)>>1, mid);
    merge(mid+1, (mid+1+r)>>1, r);

    int i = l, j = mid+1;
    _rep(k, l, r) {
        if (j > r || (i <= mid && a[i] <= a[j])) b[k] = a[i++];
        else b[k] = a[j++], ans += (mid-i+1);
    }
    _rep(k, l, r) a[k] = b[k];
}

void solve() {
    _rep(i, 1, n) scanf("%d", &a[i]);
    ans = 0;
    merge(1, (1+n)>>1, n);
    printf("%lld\n", ans);
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d", &n) == 1 && n) {
        init();
        solve();
    }
}

逆序对解决奇数码游戏

Acwing108

const int maxn = 500 + 10;
int st[maxn*maxn], b[maxn*maxn], ed[maxn*maxn];
int n, m = 0;

void merge(int l, int mid, int r, int* a, ll &cnt) {
    if (l == r) return;
    if (l + 1 == r) {
        if (a[l] > a[r]) swap(a[l], a[r]), cnt++;
        return;
    }

    merge(l, (l+mid)>>1, mid, a, cnt);
    merge(mid+1, (mid+1+r)>>1, r, a, cnt);

    int i = l, j = mid+1;
    _rep(k, l, r) {
        if (j > r || (i <= mid && a[i] <= a[j])) b[k] = a[i++];
        else b[k] = a[j++], cnt += (mid-i+1);
    }
    _rep(k, l, r) a[k] = b[k];
}

ll calc(int *A) {
    ll cnt = 0;
    merge(0, (m-1)>>1, m-1, A, cnt);
    return cnt;
}

void init() {
    m = 0;
    memset(st, 0, sizeof st);
    memset(ed, 0, sizeof ed);
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d", &n) == 1 && n) {
        init();

        // get start situation
        m = 0;
        _for(i, 0, n*n) {
            int x; scanf("%d", &x);
            if (x == 0) continue;
            st[m++] = x;
        }
        assert(m == n*n-1);

        // get end situation
        m = 0;
        _for(i, 0, n*n) {
            int x; scanf("%d", &x);
            if (x == 0) continue;
            ed[m++] = x;
        }

        assert(m == n*n-1);

        if (m == 0) {
            puts("TAK");
            return 0;
        }

        // then solve
        ll cnt1 = calc(st);
        ll cnt2 = calc(ed);


        if ((cnt1&1) == (cnt2&1)) puts("TAK");
        else puts("NIE");
    }
}

倍增

int solve(const int T) {
    int k = 0, p = 1, sum = 0;
    while (p && k <= n) {
        if (sum + S[k+p] - S[k] <= T) {
            sum = sum + S[k+p] - S[k];
            k += p, p *= 2;
        }
        else p /= 2;
    }
    return k;
}

最远扩展法

Acwing109

const int maxn = 500000 + 10;
ll dat[maxn], a[maxn], b[maxn];
int n, m;
ll T;

inline ll sq(ll x) { return x*x; }

void init() {
    memset(dat, 0, sizeof dat);
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);
}

inline void merge(int L, int mid, int R) {
    int i = L, j = mid+1;
    _rep(k, L, R) {
        if (j > R || (i <= mid && a[i] <= a[j])) b[k] = a[i++];
        else b[k] = a[j++];
    }
}

inline ll calc(int L, int r, int R) {
    if (R > n) R = n;
    int tot = min(m, (R-L+1)>>1);

    // a[r+1...R] is new segment
    _rep(i, r+1, R) a[i] = dat[i];
    sort(a+r+1, a+R+1);
    merge(L, r, R);

    // quick sort + merge sort ==> b[...] sorted
    ll val = 0;
    _for(i, 0, tot) val += sq(b[R-i] - b[L+i]);
    return val;
}

void solve(int &ans) {
    int L = 1, R = 1;
    a[1] = dat[1];

    while (L <= n) {
        int p = 1;
        while (p) {
            ll val = calc(L, R, R+p);
            if (val <= T) {
                // valid, update a[...]
                R = min(R+p, n);
                _rep(i, L, R) a[i] = b[i];
                if (R >= n) break;
                p <<= 1;
            }
            else p >>= 1;
        }

        ans++;
        L = R+1;
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;

    while (kase--) {
        init();

        // get data
        scanf("%d%d%lld", &n, &m, &T);
        _rep(i, 1, n) scanf("%lld", &dat[i]);

        // then solve
        int ans = 0;
        solve(ans);
        printf("%d\n", ans);
    }
}