4 条题解
-
6
再反复看 活动选择 与 比赛数 后,我确定了这两题就是题目说法变了,但做法不变。
因此,直接把 活动选择 的代码复制过来即可。
活动选择 AC 代码( 74ms ):
#include <cstdio> //printf using namespace std; int n , ans; int t = -1; //上一个比赛的结束时间 struct QWQ{ int bt , et; //起始时间,结束时间 }qwq[100005]; void qsort(int l , int r){ //用二分优化的冒泡排序(快排) int mid = qwq[(l + r) >> 1].et; // x >>= 1 位运算 等同于 x /= 2 int i = l , j = r; do{ while(qwq[i].et < mid) i++; while(qwq[j].et > mid) j--; if(i <= j){ QWQ t = qwq[i]; qwq[i] = qwq[j]; qwq[j] = t; i++; j--; } }while(i <= j); if(l < j) qsort(l , j); //递归 if(i < r) qsort(i , r); } int main(void){ scanf("%d" , &n); for(register int i = 0;i < n;i++) //循环加速 scanf("%d%d" , &qwq[i].bt , &qwq[i].et); qsort(0 , n - 1); //快排 for(register int i = 0;i < n;i++){ if(qwq[i].bt >= t){ ans++; t = qwq[i].et; } } printf("%d" , ans); }
-
4
</span>#include <bits/stdc++.h> using namespace std; struct hd{int begini, endi;}; hd a[1000001]; bool cmp(hd a,hd b){ return a.endi<b.endi; } int n; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].begini>>a[i].endi; }sort(a+1,a+n+1,cmp); int ans=1,cur=a[1].endi; for(int i=2;i<=n;i++){ if(a[i].begini<cur) continue; ans++; cur=a[i].endi; }cout<<ans; return 0; }//这不就跟活动选择一样吗() //这个代码在活动选择和比赛数通用
- 1
信息
- ID
- 1331
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 447
- 已通过
- 158
- 上传者