题号：1803
首先贴一种我一开始的错误做法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | #include<iostream> #include<algorithm> using namespace std; int n; struct s{ int start; int end; bool operator < (s & s1){ if (end != s1.end)return end < s1.end; else return start < s1.start; } }arr[1000005]; bool occupied[1000005]; int cnt; int main(){ ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i++)cin >> arr[i].start >> arr[i].end; sort(arr + 1, arr + n + 1); for (int i = 1; i <= n; i++){ if (!occupied[arr[i].start]){ for (int j = arr[i].start; j < arr[i].end; j++){ occupied[j] = true; } cnt++; } } cout << cnt; } |
这里的21行条件判断是错的。为什么呢？仅判断比赛开头有空闲是不能保证后面的时间有空闲的。那么我写一个正确的代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #include<iostream> #include<algorithm> using namespace std; int n; struct s{ int start; int end; bool operator < (s & s1){ if (end != s1.end)return end < s1.end; else return start > s1.start; } }arr[1000005]; int cnt; int main(){ ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i++)cin >> arr[i].start >> arr[i].end; sort(arr + 1, arr + n + 1); int t = 0; for (int i = 1; i <= n; i++){ if (t<=arr[i].start){ cnt++; t = arr[i].end; } } cout << cnt; } |
这次的21行与之前的上一个比赛结束时间进行比较，如果在结束时间后面才能开始这个比赛。
注意：数组是排过序的，以结束时间、开始时间分别升序排序。