每日一题（PTAL2）：列车调度--贪心+二分

本文主要是介绍每日一题（PTAL2）：列车调度--贪心+二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

选择去维护一个最小区间

代码1：

#include<bits/stdc++.h>
using namespace std;
int main() {int n;cin>>n;int num;vector <int> v;int res=0;for(int i=0;i<n;i++){cin>>num;int loc=v.size();int left=0;int right=v.size()-1;while(left<=right){int mid=(left+right)/2;if(num>=v[mid]){left=mid+1;}else{loc=mid;right=mid-1;}}if(loc==v.size()){res++;v.push_back(num);}else{v[loc]=num;}}cout<<res;return 0;
}

代码2：

#include<bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;int x[100005];int cnt = 0;for (int i = 0; i < n; i++) {int y;cin >> y;int *p = lower_bound(x, x + cnt, y);if (p == x + cnt) {cnt++;}*p = y;}cout << cnt << endl;return 0;
}

代码3：

#include<bits/stdc++.h>
using namespace std;
int main() {int n;cin>>n;int num;vector <int> v;int res=0;for(int i=0;i<n;i++){cin>>num;auto loc=lower_bound(v.begin(),v.end(),num);if(loc==v.end()){res++;v.push_back(num);}else{*loc=num;;}}cout<<res;return 0;
}

这篇关于每日一题（PTAL2）：列车调度--贪心+二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---