dshkjfseo优化

dshkjf

news/2024/10/24 20:59:56

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

问题分析

输入参数：
- 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 天开始，所以要排除在这之前结束的工作。