题解：P10205 [JOI 2024 Final] 室温

· · 题解

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

记得，顶一下！