CF-1136-D-Nastya Is Buying Lunch(贪心)

题目链接

https://codeforces.com/contest/1136/problem/D

题目大意

一个数列n个数,和m对可交换的数u,v,当且仅当u在v之前且中间没有其他数间隔时可交换。问最后一个数可以通过交换到达多少不同的位置。

解题思路

一开始想要建图跑搜索,后来wa了后看题解发现了一个非常重要的性质。
就是因为只能在相邻的数之间交换,所以用num[x]记录x后面可以与其交换的数的数目,当这个数与到最后一个数的距离相等时,就可以让最后一个数通过交换到达当前x的位置。
例如数据
5 11
5 1 3 4 2
5 1
5 2
1 5
2 1
1 2
1 4
2 5
1 3
5 4
5 3
3 1
后面能与1交换的数量等于1与2之间的距离2,所以1可以移动到2前面。进而让1与2交换,1与2交换后2前移了一位,所以5后面可以与2交换的数目也等于5与2之间的距离2,5也可以通过交换换到2前面,进而与2交换使2前移一位。

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int a[300030];
vector<int>mp[300030];
//unordered_map<int,int>mp;
int ans;
int num[300030];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int u,v;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v;
        mp[v].push_back(u);
    }
    ans=0;
    for(auto vv:mp[a[n-1]])
    {
        num[vv]++;
    }
    for(int i=n-2;i>=0;i--)
    {
        if(num[a[i]]==n-i-1-ans)
            ans++;
        else
        {
            for(auto vv:mp[a[i]])
            {
                num[vv]++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

1 thought on “CF-1136-D-Nastya Is Buying Lunch(贪心)”

发表评论

电子邮件地址不会被公开。 必填项已用*标注