CCF-CSP第25次认证第二题——出行计划

官网链接：TUOJ

参考题解【逻辑简单直接但时间复杂度不达标】

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;typedef pair <int, int> PII;int main () {ios::sync_with_stdio(false);cin.tie(0);int n, m, k; //计划数，查询个数，等待时间cin >> n >> m >> k;//	vector<PII> plan(n + 1); //出行计划的时刻和核酸要求 vector<PII> region(n + 1);//每个计划可行的做核酸时间范围 for(int i = 1; i <= n; i++) {int t, c;cin >> t >> c;
//		plan[i] = {t, c};region[i] = {t - k - c + 1, t - k};} sort(region.begin(), region.end());for(int i = 1; i <= m; i++) {int query;//查询，即该时刻做核酸cin >> query;int count = 0;//可行的计划数 for(int i = 1; i <= n; i++) {if(region[i].first > query) break;if(region[i].first <= query && query <= region[i].second) {count++;}} cout << count << endl;}return 0;
}

优化版【二分查找思想】

• 每个查询由原来的 O(n) 线性扫描，优化为 O(log⁡n) 的二分查找，从而整体时间复杂度降低为 O(nlog⁡n+mlog⁡n) 
• 这种方法在 n,m≤10^5 的情况下非常高效，能满足题目的时间要求。

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;typedef pair <int, int> PII;int main () {ios::sync_with_stdio(false);cin.tie(0);int n, m, k; //计划数，查询个数，等待时间cin >> n >> m >> k;vector<int> starts(n + 1), ends(n + 1); //分别存储每个计划可行的做核酸的最早时间和最晚时间 for(int i = 1; i <= n; i++) {int t, c;cin >> t >> c;starts[i] = t - k - c + 1;ends[i] = t - k;} sort(starts.begin(), starts.end());sort(ends.begin(), ends.end());while(m--) {int q;//查询，即该时刻做核酸cin >> q;// 找第一个 > q 的起点----看有多少个区间的起点<=q int cnt1 = upper_bound(starts.begin(), starts.end(), q) - starts.begin();// 找第一个 >= q 的终点，数量即 <q 的数目int cnt2 = lower_bound(ends.begin(), ends.end(), q) - ends.begin();cout << cnt1 - cnt2 << endl;}return 0;
}

总结

重难点在于理解为什么答案是 cnt1−cnt2

• cnt1cnt1cnt1： 统计所有满足 s≤q 的区间个数，即这些区间已经开始。
• cnt2cnt2cnt2： 统计所有满足 e<q 的区间个数，即这些区间已经结束（不再包含 q）。

因此，满足 s≤q≤e 的区间数量，就是“已开始但未结束”的区间数量，即：

答案=已开始区间数−已结束区间数=cnt1−cnt2