Azusa的计划｜取模&环转链

T4 - Azusa的计划

题目链接跳转：点击跳转

这道题的难度也不是很高，稍微思考一下即可。

任何事件时间 $t$ 对 $(a + b)$ 取模后，事件可以映射到一个固定的周期内。这样，问题就转化为一个固定长度的区间检查问题。

因此，在读入数字后，将所有的数字对 $(a + b)$ 取模并排序，如果数字分布（序列的最大值和最小值的差值天数）在 $a$ 范围内即可满足将所有的日程安排在休息日当中。但需要注意的是，两个日期的差值天数不能单纯地使用数字相减的方法求得。以正常 $7$ 天为一周作为范例，周一和周日的日期差值为 $1$ 天，而不是 $7 - 1 = 6$ 天。这也是本题最难的部分。

如果做过 区间 DP 的用户应该能非常快速地想到如果数据是一个 “环状” 的情况下该如何解决问题（参考题目：石子合并（标准版））。我们可以使用 “剖环成链” 的方法，将环中的元素复制一遍并将每个数字增加 $(a + b)$，拼接在原数组的末尾，这样一个长度为 $n$ 的环就被扩展为一个长度为 $2n$ 的线性数组。

最后只需要遍历这个数组内所有长度为 $n$ 的区间 $[i, n + i - 1]$，判断是否有任意一个区间的最大值和最小值的差在 $a$ 以内即可判断是否可以讲所有的日程安排都分不在休息日中。

本题的时间复杂度为 $O(N \log_2 N)$。

本题的 C++ 代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

int n, a, b;
int arr[500005];
int maximum, minimum = 0x7f7f7f7f;

int main(){
	ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> a >> b;
    for (int i=1; i<=n; i++){
    	cin >> arr[i];
        arr[i] %= (a + b);
    }
    sort(arr+1, arr+1+n);
    for (int i=1; i<=n; i++){
    	arr[i+n] = arr[i] + (a + b);
    }
    bool flag = 0;
    for (int i=1; i+n-1<=2*n; i++) {
        if (arr[i+n-1] - arr[i] < a)
            flag = 1;
    }
    cout << (flag ? "Yes" : "No") << endl;
}

本题的 Python 代码如下：

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n, a, b = map(int, data[:3])
    arr = list(map(int, data[3:]))
    
    mod_value = a + b
    arr = [x % mod_value for x in arr]
    
    arr.sort()
    
    arr += [x + mod_value for x in arr]

    flag = False
    for i in range(n):
        if arr[i + n - 1] - arr[i] < a:
            flag = True
            break

    print("Yes" if flag else "No")

if __name__ == "__main__":
    main()