codeforces 1136D Nastya Is Buying Lunch【贪心】

题目大意

有n个人，排成一列，给出m对 伙伴 x,y 表示若x恰好排在y的前方，则x,y可以互换位置，问最后一个人能够最多往前走几个位置

题目分析

假设 a[n]为最后一个人，若 a[n-1] 恰好能和她换位置，那么肯定是换位置的情况更优，因此这时候一定会选择换位置，·假设不换位置，交换到某个值后再与a[n]换位置，那么a[n-1]就错失换位置的机会，答案数就会少1，而换位置并不会改变前面的数对于a[n]位置的影响，因此此时必定选择换位置。
若是a[n-1]不能与a[n]换位置，那么考虑，如果a[n]想往前进一步，假设a[i]是最早能够使的a[n]前进的数，那么a[i]必然要与a[n]中间的所有数交换位置，因此，我们判断a[i]到a[n]之间的数是否能与a[i]交换位置，如果能，a[n]就往前前进1位，a[i]则移到a[n]后面，不再考虑

代码示例

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+50;
int n,m;
bool vis[maxn];
int a[maxn];
vector<int>v[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
    }
    memset(vis,false,sizeof(vis));
    vis[a[n]]=true;
    int  ans=0;
    for(int i=n-1;i>=1;i--)
    {
        int cnt=0;
        for(int j=0;j<v[a[i]].size();j++)
        {
            int t =v[a[i]][j];
            if(vis[t])cnt++;
        }
        if(cnt+i+ans==n)ans++;
        else vis[a[i]]=1;
    }
    cout<<ans<<endl;
    return 0;
}