P10139 [USACO24JAN] Nap Sort G 题解

· · 题解

G组练习总结#13

场切题！USACO 真的很喜欢放二分题目（笑）。

题目大意

Bessie 又在制造麻烦事！

她现在有一个长度为 n(n\le2\times10^5) 的数组 a(a_i\le10^{11})，她现在想要用自己发明的排序方法让其排好序。

具体来说，她的排序方法是：

首先，她会新建一个数组 t，用来记录排好序后的 a。

然后 Bessie 会自己选取一些数自己处理，假设她目前手上有 p 个数，她需要花费 p 的时间去找到最小的数并马上把它加入 t 的最后。

简单来说，设一开始的集合大小是 p，第一个数会在 p 时加入，第二个数会在 2p-1 时，第三个会在 3p-3 以此类推。

但她还有另一种选择，她可以把数交给朋友们来操作，朋友们很懒，假设他们拿到的数是 v，他们先睡 v，在 v 时加入 t 末尾。

加入的时候，如果 Bessie 和朋友同时加数，Bessie 优先级更高。

现在 Bessie 也想去睡觉啦（不是），她想知道最短的加入所有数的时间。

数据有 T(T\leq10) 组。

解题思路（暴力）

处理肯定按照顺序，所以我们可以直接将 a 从小到大排序。

我们考虑最后一个数 a_n 是由谁处理的，如果是 Bessie，所需要的时间就是 \frac{p(p+1)}2，如果是朋友们，那就是 a_n。

因此，我们考虑枚举集合大小 p，判断当前钦定的 p 是否可以让 a_n 被选入集合？

至于向集合内加数需要满足，比如，加第一个时，我们要把 a_i<p 的数都交给朋友们，然后把第一个 a_j\ge p 的数交给 Bessie。

为什么要这样？因为 Bessie 加入的第一个数肯定在 p 时加入，那 a_i<p 的必须满足在她之前处理完了，所以要找朋友帮忙。

而且注意，因为 Bessie 的优先级大于朋友们，所以如果她们同时在 p 加入数，必须满足 Bessie 手上的数小于或等于朋友的，固 a_j 等于 p 的情况不能漏。

对于其他的情况，也都是这样处理，依次处理完所有 p 个数，判断是否处理完了 a_n。

时间复杂度 \Theta(n\sqrt A)，A 为 a 的值域。

参考代码（暴力）

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=2e5+5;
typedef long long ll;
int t,n,c;
ll a[N],m,p;
int main() {
    int i,j;
    scanf("%d",&t);
    while(t) {
        --t;
        scanf("%d",&n);
        for(i=1; i<=n; ++i)
            scanf("%lld",a+i);
        sort(a+1,a+n+1);
        m=a[n];
        for(j=1; 1ll*(j+1)*j/2<=a[n]; ++j) {//枚举集合大小p
            c=j;
            p=0;
            for(i=1; i<=n; ++i) {
                if(!c)
                    break;
                if(a[i]>=p+c) {//依次往集合里面塞数
                    p=p+c;//记录当前Bessie加数的时间
                    --c;
                }
                if(i==n)
                    m=min(m,1ll*j*(j+1)/2);//找答案
            }
            if(m<a[n])
                break;
        }
        printf("%lld\n",m);
    }
    return 0;
}

解题思路（正解）

突然发现几乎没有什么好说的啊……

这个题目的答案具有单调性啊，集合大小的可行性是有单调性的？

没错，这个也挺好想的，越大的集合我们就可以处理更多数！

这么好的代码（不是），一改就可以适应一个二分对吧！

新的时间复杂度 \Theta(n\log_2\sqrt A)，完结撒花(●'◡'●)！

参考代码（正解）

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=2e5+5;
typedef long long ll;
int t,n,l,r,d;
ll a[N],m,p;
int check(int c) {
    int i;
    p=0;
    for(i=1; i<=n; ++i) {
        if(!c)
            return 0;
        if(a[i]>=p+c) {
            p=p+c;
            --c;
        }
    }
    return 1;
}
int main() {
    int i,j;
    scanf("%d",&t);
    while(t) {
        --t;
        scanf("%d",&n);
        for(i=1; i<=n; ++i)
            scanf("%lld",a+i);
        sort(a+1,a+n+1);
        m=a[n];
        l=1,r=sqrt(a[n]);
        while(l<=r) {//只不过改了，枚举变成二分就好啦~
            d=l+r>>1;
            if(check(d)) {
                r=d-1;
                m=1ll*d*(d+1)/2;
            } else
                l=d+1;
        }
        printf("%lld\n",m);
    }
    return 0;
}