企业官网建设流程全解析

P11208 『STA - R8』轮回疯狂

题目描述

给一个111到nnn的排列ppp，你可以使用两种操作：

• 轮回：交换ppp中相邻的两个位置。
• 疯狂：删除ppp中的最小值。如果ppp为空则不能进行操作。

问最少需要多少次操作才能使得序列单调递增。

输入格式

第一行一个正整数nnn。

第二行nnn个正整数，描述排列ppp。

输出格式

一行一个正整数，表示答案。

输入输出样例 #1

输入 #1

3 3 2 1

输出 #1

2

说明/提示

样例解释：先删除p3p_3p3​，再交换p1,p2p_1,p_2p1​,p2​。

本题采用捆绑测试。

数据范围：

• Subtask 1 (10pts)：n≤3n\le 3n≤3。
• Subtask 2 (30pts)：n≤103n\le 10^3n≤103。
• Subtask 3 (10pts)：pi=n−i+1p_i=n-i+1pi​=n−i+1。
• Subtask 4 (50pts)：无特殊限制。

对于全部数据，1≤n≤1051\le n\le 10^51≤n≤105，ppp是111到nnn的排列。

C++实现

#include<iostream>usingnamespacestd;constintN=100010;intn;inta[N],pos[N];intinvension[N];structBIT{intc[N];#definelowbit(x)(x&-x)inlinevoidadd(intx,intv){for(;x<=n;x+=lowbit(x))c[x]+=v;}inlineintask(intx){intres=0;for(;x;x-=lowbit(x))res+=c[x];returnres;}}tr1,tr2;//封装数据结构intmain(){scanf("%d",&n);for(inti=1;i<=n;i++){scanf("%d",&a[i]);pos[a[i]]=i;//记录每个数出现在哪个位置}longlongsum=0;for(inti=n;i;i--){invension[i]=tr1.ask(a[i]-1);sum+=invension[i];tr1.add(a[i],1);}longlongans=min(sum,(longlong)n-1);for(inti=1;i<=n;i++)tr2.add(i,1);//一开始每个位置上都有数for(inti=1;i<n;i++){intcnt=tr2.ask(pos[i]-1);sum-=cnt;ans=min(ans,(longlong)sum+i);tr2.add(pos[i],-1);//删掉后这个位置上就没有数了}printf("%lld",ans);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容