8 solutions
-
0
这道题首先我们要得到最多能够开展多少活动,我的想法是将每个活动的时间以右边界为标准,按升序来排序,根据贪心的思想,我肯定得优先选择右边界最小的,然后从右边界最小的里面来匹配,看此时他的左边界是否符合要求,并且计数
不多说 来看代码:#include <bits/stdc++.h> using namespace std; pair<int,int>pa[1005]; bool cmp(pair<int,int>a,pair<int,int>b) { return a.second<b.second; } int main() { int n; cin>>n; for(int i=1;i<=n;++i) { cin>>pa[i].first>>pa[i].second; } sort(pa+1,pa+n+1,cmp); int cnt = 1; int r = pa[1].second;//先确定最小的右边界 for(int i=1;i<=n;++i) { if(pa[i].first>=r){ cnt++; r=pa[i].second;//每次匹配成功,将cnt++并且更新新的右边界 } } cout << cnt << endl; }
Information
- ID
- 91
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 6
- Tags
- # Submissions
- 198
- Accepted
- 60
- Uploaded By