dshkjf

标签：dshkjf 重叠访问 ss 天到工作 es

这道题目要求我们为罗宾的兄弟和母亲选择最佳的访问起始日期，以使兄弟的访问与最多的工作重叠，而母亲的访问与最少的工作重叠。下面是解题思路的详细讲解：

问题分析

输入参数：
- n: 总天数
- d: 访问持续天数
- k: 工作数量
- 接下来是 k 行，描述每个工作对应的起止日期 [l_i, r_i]。
访问安排：
- 罗宾的兄弟访问从某一天开始，持续 d 天，所有访问的天数必须在 1 到 n 之间。
- 母亲的访问也是如此。
目标：
- 找到兄弟的最佳开始日，使得他与最多的工作重叠。
- 找到母亲的最佳开始日，使得她与最少的工作重叠。
- 如果有多个选择，选择最早的那一天。

解题步骤

使用前缀和：
- 通过前缀和数组，我们可以高效地计算在任何区间内有多少个工作重叠。
- 我们定义两个数组：ss（开始工作数量）和 es（结束工作数量）。
- 对于每个工作 [l_i, r_i]，我们在 ss[l_i] 增加 1，表示工作在 l_i 开始，在 es[r_i + 1] 减少 1，表示在 r_i 之后结束。
计算前缀和：
- 利用前缀和将 ss 和 es 转化为从第 1 天到第 n 天的累计工作开始和结束数。
滑动窗口：
- 计算每个可能的访问开始日，检查与之重叠的工作数量。
- 对于每个可能的访问日 i，我们检查 ss[i] - es[i - d]，得到区间 [i, i + d - 1] 的重叠工作数。
寻找最佳日期：
- 在遍历所有可能的开始日时，记录兄弟的最大重叠日和母亲的最小重叠日。

实现代码

下面是根据上述思路的实现代码，和你之前给出的代码基本一致：

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

void work() {
    int n, k, d;
    cin >> n >> d >> k;
 
    vector<int> ss(n + 1), es(n + 1);
 
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        ss[a]++;
        es[b + 1]++; // 结束的下一天
    }
 
    for (int i = 1; i <= n; i++) {
        ss[i] += ss[i - 1];
        es[i] += es[i - 1];
    }
 
    int most = 0, robert = 1; // 最大重叠
    int least = 1e9, mrs = 1; // 最小重叠

    for (int i = 1; i <= n - d + 1; i++) {
        int cur = ss[i + d - 1] - es[i - 1];
        if (cur > most) {
            most = cur;
            robert = i;
        }
        if (cur < least) {
            least = cur;
            mrs = i;
        }
    }

    cout << robert << ' ' << mrs << "\n";
}
 
int main() {
    int t;
    cin >> t;
    while (t--) work();
    return 0;
}

复杂度分析

时间复杂度：O(n + k) 每个测试用例中，处理前缀和和遍历天数。
空间复杂度：O(n) 用于存储前缀和数组。

总结

通过前缀和和滑动窗口技术，我们能够高效地计算每个可能的访问开始日与工作重叠的情况，从而找到最佳的开始日期。这种方法对于大规模数据的处理非常高效。

这行代码的目的是计算从第 i 天开始，持续 d 天的访问期间内，重叠的工作数量。

具体解释

ss[i + d - 1]：这是到第 i + d - 1 天（即访问结束的那一天）为止的开始工作数量的累计和。它表示在这 d 天期间（从第 i 天到第 i + d - 1 天）开始的所有工作数量。
es[i - 1]：这是到第 i - 1 天的结束工作数量的累计和。它表示在第 i 天之前结束的所有工作数量。因为母亲的访问在第 i 天开始，所以要排除在这之前结束的工作。

组合起来的含义

cur = ss[i + d - 1] - es[i - 1] 计算的是在访问期间 [i, i + d - 1] 内的所有重叠工作数。具体来说，它通过计算在结束日的工作开始数减去在开始日之前结束的工作数，从而得到该区间内独特工作的数量。

例子

假设有以下工作安排：

工作1：从第1天到第2天
工作2：从第2天到第3天
工作3：从第4天到第5天

如果你想计算从第2天开始持续2天的访问（即访问区间是第2天到第3天）：

ss[3]（第3天的开始工作数量）可能是2（工作1和工作2都在第2天开始）。
es[1]（第1天结束的工作数量）可能是0（没有工作在第1天结束）。

因此：

cur = ss[3] - es[1] = 2 - 0 = 2，表示在第2天到第3天这段时间，有2个工作重叠。

这个计算方法确保了我们得到的是在这个访问期间内的独特工作数量，而不重复计算那些在访问之前已经结束的工作。

标签：dshkjf,重叠,访问,ss,天到,工作,es
From： https://www.cnblogs.com/xkgc/p/18500460