找每个元素开始到结尾的最小值
方法2:思路同上差不多
用一个数组a[i]存储从i开始到结尾的最小值
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
typedef pair<int ,int> PII;
PII p[N];
int a[N];
int n;
int main(){
cin>>n;
int x,v;
for(int i=0;i<n;i++)
{
scanf("%d%d",&x,&v);
p[i] = {x,v};
}
sort(p,p+n);//先排序,再找最小值a和p才能对应上
a[n-1] = p[n-1].second;
for(int i=n-2;i>=0;i--) a[i] = min(a[i+1],p[i].second);
int l=0,ans = 0;
for(int i=0;i<n;i++)
{
int ps = p[i].second;
if(ps <= a[i])
{
ans++;
}
}
cout<<ans;
return 0;
}
方法2:想的太复杂,未过
//思路:用一个数组存贮出现过发速度,并排好序,用pair p存<x,v>, 遍历p,当右边有比自己小的数时ans++
//困难:如何删去vector指定元素
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
using namespace std;
const int N = 100010;
typedef pair<int ,int> PII;
PII p[N];
int n;
int main(){
cin>>n;
unordered_map<int ,int> mp;//存当前位置右边仍存在的每个v的个数
vector<int> a;//存储当前位置右边仍存在的v的最小值
int x,v;
for(int i=0;i<n;i++)
{
scanf("%d%d",&x,&v);
p[i] = {x,v};
if(!mp.count(v)) a.push_back(v);
mp[v] += 1;
}
sort(p,p+n);
sort(a.begin(),a.end());
int l=0,ans = 0;
for(int i=0;i<n;i++)
{
int ps = p[i].second;
if(ps <= a[0])
{
ans++;
mp[ps] -= 1;
}
else mp[ps] -= 1;
if(!mp.count(ps))
}
cout<<ans;
return 0;
}