专栏文章

题解：P10139 [USACO24JAN] Nap Sort G

cchenwenmo
P10139题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioicxci
此快照首次捕获于
2025/12/02 19:41
3 个月前
此快照最后确认于
2025/12/02 19:41
3 个月前
查看原文

提供一个瓶颈是基数排序的做法

首先对原数组排序，方便考虑。
考虑先枚举 Bessie 堆的大小 mm，
如果 ana_n 是助手堆的，那么答案就是 ana_n；否则答案是 m⋅(m+1)2\frac{m\cdot(m+1)}{2}。因此强制让 ana_n 放入 Bessie 堆。
那么现在的问题就是 check mm 是否存在包含 ana_n 的合法方案。
在一个方案中，Bessie 堆的数把原序列划分成若干段，那么原序列中助手堆的数，会有对应的合法值域区间，每个助手堆中的数必须在相应区间中，方案才能合法。
因此我们可以 O(n)O(n) 从后往前分段。假设枚举到 aia_i，如果 aia_i 是在当前合法值域区间里，就把 aia_i 分到这一段，否则 aia_i 就设为这一段的左端点（即把 aia_i 放入 Bessie 堆中），然后考虑 ai−1a_{i-1}。放完最后一个 Bessie 数后，再 check 序列前面剩下的一些数是否在合法区间中，即可。这样做是 O(n2)O(n^2) 的。
这样做其实非常麻烦，因为我们只关心是否存在方案，而不关心具体方案。
考虑不合法的情况长什么样。已经选了 ana_n，考虑 an−1a_{n-1}，如果 an−1<∑j=1mja_{n-1}<\sum\limits_{j=1}^{m}j，这就意味着 a1,a2,…,an−1a_1,a_2,\dots,a_{n-1} 是一定存在方案的，不用再往前分段考虑了。
否则，我们就必须选 an−1a_{n-1}，然后继续依次往前考虑 an−xa_{n-x}，直到 an−x<∑j=xmja_{n-x}<\sum\limits_{j=x}^{m}j。
也就是说，mm 合法，当且仅当存在 i∈[n−m,n−1]i\in[n-m,n-1]，使得 ai<∑j=n−imja_{i}<\sum\limits_{j=n-i}^{m}j。于是就有了更简便的 O(n2)O(n^2) 写法。
CPP
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 2e5 + 5;

int n;
LL a[N], b[N];

LL sum(int l, int r) {
    return b[r] - b[l - 1];
}

void solve() {
    read(n);
    for (int i = 1; i <= n; i++) {
        read(a[i]);
        b[i] = b[i - 1] + i;
    }
    sort();
    LL ans = a[n];
    for (int i = 1; i <= n; i++) {
        for (int j = n; j >= n - i + 1; j--) {
            if (a[j - 1] < sum(n - j + 1, i)) {
                ans = min(ans, sum(1, i));
            }
        }
    }
    printf("%lld\n", ans);
}
继续考虑优化，发现 i,ji,j 可以交换枚举顺序，然后二分，即可做到 O(nlog⁡n)O(n\log n)。
CPP
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 2e5 + 5;

int n;
LL a[N], b[N];

LL sum(int l, int r) {
    return b[r] - b[l - 1];
}

void solve() {
    read(n);
    for (int i = 1; i <= n; i++) {
        read(a[i]);
        b[i] = b[i - 1] + i;
    }
    sort();
    LL ans = a[n];
    for (int i = 1; i <= n; i++) {
        int len = n - i + 1, l = len, r = n, mid;
        while (l < r) {
            mid = l + r >> 1;
            if (a[i - 1] < sum(len, mid)) r = mid;
            else l = mid + 1;
        }
        if (a[i - 1] < sum(len, r)) {
            ans = min(ans, sum(1, r));
        }
    }
    printf("%lld\n", ans);
}
更快的做法就是，用初中二次函数相关知识，推一下式子，做到 O(1)O(1) 求，那么复杂度瓶颈就是 sort 了，求答案是 O(n)O(n) 的。然后我选择 256256 进制的基数排序，即可做到非常接近线性。
完整代码：
提交记录
CPP
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using DB = double;

namespace FIO {
    char buf[1 << 20], *_now = buf, *_end = buf;
    inline char _getchar() {
        return _now == _end && (_end = (_now = buf) + fread(buf, 1, 1 << 20, stdin), _now == _end) ? EOF : *_now++;
    }
    
    template <typename T>
    void read(T &x) {
        x = 0;
        char c = getchar();
        for (; c < '0' || c > '9'; c = getchar());
        for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + (c ^ 48), c = getchar());
    }
} using FIO::read;

const int N = 2e5 + 5;

int n;
LL a[N], b[N];

LL sum(int l, int r) {
    return b[r] - b[l - 1];
}

// 基数排序
int cnt[260];
LL tmp[N];
void sort() {
    for (int i = 0; i <= 40; i += 8) {
		memset(cnt, 0, sizeof(cnt));
		for (int j = 1; j <= n; j++) cnt[(a[j] >> i) & 255]++;
		for (int j = 1; j < 256; j++) cnt[j] += cnt[j - 1];
		for (int j = n; j >= 1; j--) tmp[cnt[(a[j] >> i) & 255]--] = a[j];
		for (int j = 1; j <= n; j++) a[j] = tmp[j];
	}
}

void solve() {
    read(n);
    for (int i = 1; i <= n; i++) {
        read(a[i]);
        b[i] = b[i - 1] + i;
    }
    sort();
    LL ans = a[n];
    for (int i = 1; i <= n; i++) {
        int len = n - i + 1;
        LL x = a[i - 1] + a[i - 1] + (LL)len * len - len;
        LL dlt = x + x + x + x + 1;
        if (dlt < 0) {
            ans = min(ans, sum(1, len));
            continue;
        }
        LL k = floor((-1 + sqrt(dlt)) / 2 + 1);
        if (k <= n) {
            ans = min(ans, sum(1, max((int)k, len)));
        }
    }
    printf("%lld\n", ans);
}

int main() {
    int T;
    read(T);
    while (T--) solve();
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...