就直接
直接双队列了,草草写了个代码,中间再有问题不管了,顺带温习了一下之前内容
(共36行,有个特判我觉的应该能优化)
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
struct data{
int x,y;
bool operator < (data b){
return x<b.x;
}
};
int main(){
ios::sync_with_stdio(false);
deque<int> q;
int n;
cin>>n;
if(n==0){
cout<<"0";
return 0;
}
vector<data> v(n);
for(int i=0;i<n;++i){
cin>>v[i].x>>v[i].y;
}
sort(v.begin(),v.end());
q.push_back(v[0].y);
int ti=0;
for(int i=1;i<n;++i){
while(ti>=0&&v[i].y>q[ti]){
q.pop_back();
ti--;
}
ti++;
q.push_back(v[i].y);
}
cout<<n-q.size();
return 0;
}
using namespace std;
#pragma GCC optimize(2)
struct data{
int x,y;
bool operator < (data b){
return x<b.x;
}
};
int main(){
ios::sync_with_stdio(false);
deque<int> q;
int n;
cin>>n;
if(n==0){
cout<<"0";
return 0;
}
vector<data> v(n);
for(int i=0;i<n;++i){
cin>>v[i].x>>v[i].y;
}
sort(v.begin(),v.end());
q.push_back(v[0].y);
int ti=0;
for(int i=1;i<n;++i){
while(ti>=0&&v[i].y>q[ti]){
q.pop_back();
ti--;
}
ti++;
q.push_back(v[i].y);
}
cout<<n-q.size();
return 0;
}