Photo from Pexels
题目大意是说有n个数1到n，它们按照一定的顺序排列。然后现在有m个数对\((u,v)\)，意思是说，如果数字u排在数字v的前面(左边)，且两个数字相邻，那么两个数字就可以交换位置。问，对于排在最后的数字，通过这样的交换位置的操作，这个数字最多可以前进多少个位置(向左移动多少次)。
emmmmmmm比赛时真的没想出来......后期补题的时候也没想出来OTZ，于是不得不去看题解hhhhh
先说说我的想法:首先这题第一感觉是一道贪心题，那我们是否可以通过找到一个最长的“连续交换序列”来实现最后一个数尽可能多地向前移动呢？所谓的连续交换序列就是说，在这个序列里，前后两个交换操作是连续的，执行完前一个操作后恰好可以执行下一个操作.......emmmmmm事实证明这是个非常错误的想法，而且也不好实现
所以正确的做法应该是，记录每一个数后面有多少个可以与他交换的数，用一个cnt数组来记录。对于一个数，如果最后一个数\(x=que[i]\)与这个数的距离，即\(n-ans-i\)(\(ans\)是最后一个数目前所移动了的距离)刚好和\(cnt[x]\)相等，那就说明一定有一种操作可以将x换到这个数当前所在的位置,这是就ans++;如果不相等，那么更新以下cnt数组。非常巧妙的做法呢。
代码如下:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int que[3*maxn];
vector<int> vec[3*maxn];
int cnt[3*maxn];
int main()
{
int n,m;
cin>>n>>m;mst(cnt,0);
for(int i=1;i<=n;i++)
cin>>que[i];
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
vec[v].push_back(u);
}
for(int i=0;i<vec[que[n]].size();i++)
cnt[vec[que[n]][i]]++;
int ans=0;
for(int i=n-1;i>=1;i--){
if(cnt[que[i]]==n-ans-i){
ans++;
}else{
for(int j=0;j<vec[que[i]].size();j++)
cnt[vec[que[i]][j]]++;
}
}
cout<<ans<<endl;
}