Codeforces Round #441 D. Sorting the Coins（模拟）-白红宇

Codeforces Round #441 D. Sorting the Coins（模拟）

阅读量：4307 次

发布时间：2019-06-06

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

题意：

题意真是难懂，就是给一串序列，第i次操作会在p[x]（1<=x<=i）这些位置放上硬币，然后从左到右观察，如果第i个位置有硬币但第i+1个位置没有硬币，那么互换，然后继续从第i+1个硬币开始看。直到不需要交换，需要计算出到终极状态需要多少步。

思路：

模拟。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             10 #include
              
               11 using namespace std;12 typedef long long ll;13 typedef pair
               
                 pll;14 const int INF = 0x3f3f3f3f;15 const int maxn = 300000+5;16 17 int n;18 int p[maxn];19 int a[maxn];20 vector
                
                  ans;21 22 int main()23 {24 //freopen("in.txt","r",stdin);25 while(~scanf("%d",&n))26 {27 ans.clear();28 memset(a,0,sizeof(a));29 for(int i=1;i<=n;i++) scanf("%d",&p[i]);30 int max_right=n;31 int cnt=0;32 for(int i=1;i<=n;i++)33 {34 a[p[i]]=1;35 if(p[i]==max_right)36 {37 for(int j=max_right-1;j>=1;j--)38 {39 if(!a[j]) {max_right=j;break;}40 else cnt--;41 }42 }43 else44 {45 cnt++;46 }47 ans.push_back(cnt+1);48 }49 printf("1");50 for(int i=0;i

转载于:https://www.cnblogs.com/zyb993963526/p/7679291.html

你可能感兴趣的文章