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(logn) 的二分查找,从而整体时间复杂度降低为 O(nlogn+mlogn)
- 这种方法在 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