自动搬运

查看原文

来自洛谷，原作者为

	红尘万李 （进主页，删.cn，按Enter，即可浏览主页）不要在意他人对你说什么，你独一无二，你是你自己的光。

搬运于2025-08-24 22:55:44，当前版本为作者最后更新于2024-06-11 22:25:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P10205 [JOI 2024 Final] 室温 题解

题面传送门

题意概括

题目让我们求的是，对于一个内部任意某些元素可以减少正定值的数组 $a$，满足 $k=|a_i-t|(1≤i≤n)$ 的最大值最小，并输出这个最小的 $k$。$t$ 即为题目中的室温，可以根据需要任意修改。

题目分析

由于每一位高管的舒适温度可以通过穿外套的方式减少，我们不妨对他们进行统一：让每位高管的舒适温度都处于 $[0,t]$ 之间。这里我们可以直接通过对 $a_i$ 取模来实现，很好理解。

接下来，我们要考虑把室温 $t$ 调到哪里才能使 $k$ 最小。首先，我们将统一好的舒适温度由小到大排序。接下来，找到相邻两个高管间舒适温度相差的最大值。注意，舒适温度最低的高管和舒适温度最高的高管也要进行比较，具体方法为将最低的舒适温度 $a_1$ 加上 $t$ 后再与 $a_n$ 相减，形成一个闭环。千万不能漏掉这里。

这时候肯定就有人要问了，为什么要算这么一个最大值呢？我们可以这样理解：如果我们要调整室温使房间的不舒适度最小，那我们肯定是去成全两个相邻舒适温度相差最大的，这样才能降低最大的 $k$，从而使得房间的 $k$ 最小。

那么，上述的效果如何实现呢？我们假设已经找到两个相差最大的舒适温度，分别为 $x$ 和 $y(x<y)$，那么差的最大值即为 $maxd=y-x$。因为高管们每次改变舒适温度的值是相同的，所以最终，房间内高管舒适温度的极差的最小值，就是 $x+t-y$。

最后，我们只需要把室温调到 $[y,x+t]$ 的中间就可以了。这时的 $k$ 是 $\frac{x+t-y}{2}$，即 $\frac{t-maxd}{2}$，有可能是一个小数，但题目中要我们调至整数。此时，不管是向上取整还是向下取整，我们不舒适度的最大值都是前者。原因是，如果调整室温偏向两个高管中的一个，使其不舒适度减小，那么室温离另一个高管的舒适温度就会更远，其不舒适度就会增大。而我们取的是不舒适度的最大值，所以对于有小数的情况，不舒适度的最大值都是向上取整，具体实现可参考下面的代码。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[500002],t,maxd,k;//变量名如题意
int main()
{
    scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i]%=t;//边输入边取模
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
		maxd=max(maxd,a[i+1]-a[i]);
	maxd=max(maxd,a[1]+t-a[n]);//如题目分析，这里千万不能漏
	k=ceil((double(t-maxd))/2.0);//向上取整的函数，如果它本来就是整数就不变
	printf("%d",k);
	return 0;
}

记得，顶一下！