Codeforces-Round#546(Div.2)-D-Nastya Is Buying Lunch-白红宇

Codeforces-Round#546(Div.2)-D-Nastya Is Buying Lunch

阅读量：4946 次

发布时间：2019-06-11

本文共 941 字，大约阅读时间需要 3 分钟。

这个题官方tag是贪心，其实我觉得有点牵强，还是算思维题吧，但是自己的菜是没得说的QAQ

做的时候能想到从后向前看，如果n-1能交换就交换，不能就看n-2，依次往前。

其实再深究就会发现，如果pi和pn的距离等于pi到pn之间（包括pn）与pi可交换的个数，那么pn一定可以前进。

例如：

5 2

3 1 5 4 2

5 2

5 4

这组中5的位置和2差距是2，且可与2，4两个交换，那么就可以使pn前进。

然后有一个地方需要考虑下，这个题会输入2 5这种交换，也就是说不能在输入的时候直接处理出来pi后面的可交换的个数

那么如果确定了pi没有成为那个被换到pn后面的数（比如例子中的4），那么4前面的pi在计算可交换个数时要考虑4。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 using namespace std;const int maxn=300000+5;int n,m,u,v;vector
                 
                   edge[maxn];int arr[maxn],num[maxn];int main(){ scanf("%d%d",&n,&m); memset(num,0,sizeof(num)); for(int i=1;i<=n;i++) scanf("%d",&arr[i]); for(int i=1;i<=m;i++){ scanf("%d%d",&u,&v); edge[v].push_back(u); } for(int i=0;i
                  
                   =1;i--){ if(pos-i==num[arr[i]]) pos--; else for(int j=0;j

转载于:https://www.cnblogs.com/JustDoA/p/10569037.html

你可能感兴趣的文章