https://codeforces.com/contest/1136/problem/D
贪心 + 思维
题意
你面前有一个队列,加上你有n个人(n<=3e5),有m(m<=个交换法则,假如u在v相邻前面,那么u和v可以交换位置,问你是队列最后一个人的时候你最前可以换到前面哪里
题解
- 因为相邻才能换,所以最后一个换到前面一定是一步一步向前走,所以不存在还要向后走的情况
- 设最后一个为u,假设前面有一个能和u换位置的集合,那么需要将这些点尽量往后移动去接u
- 假设前面有一个不能和u换位置的集合S,那么u和S的顺序永远不会换过来
- 从后向前遍历,对于每个点假设后面紧接着S+u,假如这个点能和S+u换位置,那么u可以向前移动一格,ans++
- 假如不行,则将这个加入S
#include<bits/stdc++.h>
using namespace std;
int n,m,a[300005],u,v,i,ok,ans;
vector<int>A;set<pair<int,int> >vi;
int main(){
cin>>n>>m;
for(i=1;i<=n;i++)cin>>a[i];
for(i=0;i<m;i++){
cin>>u>>v;
vi.insert(make_pair(u,v));
}
A.push_back(a[n]);
for(i=n-1;i>=1;i--){
ok=1;
for(auto x:A){
if(!vi.count(make_pair(a[i],x))){ok=0;break;}
}
if(ok)ans++;
else A.push_back(a[i]);
}
cout<<ans;
}