自动搬运

查看原文

来自洛谷，原作者为

	IamZZ 博士，无须担心，答案就藏在下一次尝试中！

搬运于2025-08-24 22:55:05，当前版本为作者最后更新于2024-03-21 16:02:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}