算法标签

数学分析、排序、滑动窗口、取模运算

题解

问题分析

题目要求找到一个整数温度 ( x )，使得所有高管通过调整外套数量（每件外套降低舒适温度 ( T ) 度）后的最小不舒适度的最大值最小。核心在于：

• 每位高管的最优外套数量 ( k ) 满足 ( A_i - kT ) 尽可能接近 ( x )，即 ( k = \lfloor \frac{A_i - x}{T} \rfloor ) 或邻近值
• 不舒适度为 ( |x - (A_i - kT)| )，其最小值等价于 ( x ) 与最近的 ( A_i \mod T ) 同余类的距离

关键 insight

1. 同余类性质：对于高管 ( i )，调整外套后舒适温度为 ( A_i - kT \equiv A_i \mod T )，即所有可能的舒适温度构成以 ( A_i \mod T ) 为代表的同余类（公差为 ( T )）。
2. 距离最小化：高管 ( i ) 的最小不舒适度是 ( x ) 到最近的 ( A_i \mod T + mT )（( m ) 为整数）的距离，等价于 ( x \mod T ) 到 ( A_i \mod T ) 的环形距离（在 ( [0, T) ) 范围内）。
3. 最大值最小化：问题转化为找到一个 ( r \in [0, T) )，使得 ( r ) 到所有 ( A_i \mod T ) 的最大环形距离最小，再将该距离向上取整（因 ( x ) 必须为整数）。

算法步骤

1. 提取关键点位：计算所有 ( A_i \mod T )，并复制一份加 ( T )（处理环形边界），得到数组 dot。
2. 排序与滑动窗口：对 dot 排序后，用大小为 ( n ) 的滑动窗口找最小窗口长度。窗口长度对应最大距离的两倍（环形距离的线性化）。
3. 计算结果：最小窗口长度的一半（向上取整）即为答案。

代码解析

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
int n, T, a[N], dot[N], tot;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> T;

    // 收集所有 A_i mod T 及其 +T 的值（处理环形）
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        int mod = a[i] % T;
        dot[++tot] = mod;          // 原余数
        dot[++tot] = mod + T;      // 加 T 用于环形展开
    }

    // 排序便于滑动窗口找最小区间
    sort(dot + 1, dot + tot + 1);
    int ans = T;  // 初始最大值为 T（最坏情况）

    // 滑动窗口：找长度为 n 的窗口的最小跨度
    for (int l = 1; l <= tot - n + 1; l++) {
        ans = min(ans, dot[l + n - 1] - dot[l]);
    }

    // 最大距离为窗口跨度的一半（向上取整）
    cout << (ans + 1) / 2;
    return 0;
}

复杂度分析

• 时间复杂度：( O(N \log N) )，主要来自排序步骤。
• 空间复杂度：( O(N) )，用于存储 dot 数组。

该算法利用同余类和环形距离的性质，将复杂的温度优化问题转化为简单的滑动窗口问题，高效解决了大规模数据的需求。