企业官网建设流程全解析

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总贴：USACO历年青铜组真题解析 | 汇总-CSDN博客

【题目来源】

洛谷：[P9959 USACO19JAN] Sleepy Cow Sorting B - 洛谷

【题目描述】

Farmer John正在尝试将他的N头奶牛**( 1 ≤ N ≤ 100 ) (1\le N\le 100)(1≤N≤100)，方便起见编号为1 … N 1\dots N1…N**，在她们前往牧草地吃早餐之前排好顺序。

当前，这些奶牛以**p 1 , p 2 , p 3 , … , p N p_1,p_2,p_3,\dots,p_Np1​,p2​,p3​,…,pN​的顺序排成一行，Farmer John站在奶牛p 1 p_1p1​前面。他想要重新排列这些奶牛，使得她们的顺序变为1 , 2 , 3 , … , N 1,2,3,\dots,N1,2,3,…,N**，奶牛1 11在Farmer John旁边。

今天奶牛们有些困倦，所以任何时刻都只有直接面向Farmer John的奶牛会注意听Farmer John的指令。每一次他可以命令这头奶牛沿着队伍向后移动k kk步，k kk可以是范围**1 … N − 1 1\dots N-11…N−1**中的任意数。她经过的k kk头奶牛会向前移动，腾出空间使得她能够插入到队伍中这些奶牛之后的位置。

例如，假设N = 4 N=4N=4，奶牛们开始时是这样的顺序：

FJ:4 44,3 33,2 22,1 11

唯一注意FJ指令的奶牛是奶牛4 44。当他命令她向队伍后移动2 22步之后，队伍的顺序会变成：

FJ:3 33,2 22,4 44,1 11

现在唯一注意FJ指令的奶牛是奶牛3 33，所以第二次他可以给奶牛3 33下命令，如此进行直到奶牛们排好了顺序。

Farmer John急欲完成排序，这样他就可以回到他的农舍里享用他自己的早餐了。请帮助他求出将奶牛们排好顺序所需要的最小操作次数。

【输入】

输入的第一行包含N NN。

第二行包含N NN个空格分隔的整数，p 1 , p 2 , p 3 , … , p N p_1,p_2,p_3,\dots,p_Np1​,p2​,p3​,…,pN​，表示奶牛们的起始顺序。

【输出】

输出一个整数，为Farmer John采用最佳策略可以将这N NN头奶牛排好顺序所需要的操作次数。

【输入样例】

4 1 2 4 3

【输出样例】

3

【算法标签】

《洛谷 P9959 Sleepy Cow Sorting》 #排序# #USACO# #O2优化# #2019#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intn;inta[105];ifstreamfilein("sleepy.in");ofstreamfileout("sleepy.out");intmain(){// cin >> n;filein>>n;// 输入nfor(inti=1;i<=n;i++)// 遍历n个数filein>>a[i];// 输入至a数组中intans=n-1;// 最多调整n-1次，如1 2 5 4 3for(inti=n-1;i>=1;i--)// 从倒数第二个位置向前遍历{if(a[i]<a[i+1])// 如果从后往前发现是连续递减，则每找到一个递减的数ans--;// 结果减1else// 满足该条件，说明前面i个数都要挪到最后，需要进行i次操作break;}fileout<<ans<<'\n';// 输出结果return0;}

【运行结果】

4 1 2 4 3 3