打卡信奥刷题（3554）用C++实现信奥题 P11208 『STA - R8』轮回疯狂

P11208 『STA - R8』轮回疯狂题目描述给一个111到nnn的排列ppp你可以使用两种操作轮回交换ppp中相邻的两个位置。疯狂删除ppp中的最小值。如果ppp为空则不能进行操作。问最少需要多少次操作才能使得序列单调递增。输入格式第一行一个正整数nnn。第二行nnn个正整数描述排列ppp。输出格式一行一个正整数表示答案。输入输出样例 #1输入 #13 3 2 1输出 #12说明/提示样例解释先删除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)pin−i1p_in-i1pi​n−i1。Subtask 4 (50pts)无特殊限制。对于全部数据1≤n≤1051\le n\le 10^51≤n≤105ppp是111到nnn的排列。C实现#includeiostreamusingnamespacestd;constintN100010;intn;inta[N],pos[N];intinvension[N];structBIT{intc[N];#definelowbit(x)(x-x)inlinevoidadd(intx,intv){for(;xn;xlowbit(x))c[x]v;}inlineintask(intx){intres0;for(;x;x-lowbit(x))resc[x];returnres;}}tr1,tr2;//封装数据结构intmain(){scanf(%d,n);for(inti1;in;i){scanf(%d,a[i]);pos[a[i]]i;//记录每个数出现在哪个位置}longlongsum0;for(intin;i;i--){invension[i]tr1.ask(a[i]-1);suminvension[i];tr1.add(a[i],1);}longlongansmin(sum,(longlong)n-1);for(inti1;in;i)tr2.add(i,1);//一开始每个位置上都有数for(inti1;in;i){intcnttr2.ask(pos[i]-1);sum-cnt;ansmin(ans,(longlong)sumi);tr2.add(pos[i],-1);//删掉后这个位置上就没有数了}printf(%lld,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容