HDU5122
目录
一、题目链接
二、题干内容
Nervending is an ACMer.
Yesterday, NE learnt an algorithm: Bubble sort. Bubble sort will compare each pair of adjacent items and swap them if they are in the wrong order. The process repeats until no swap is needed.
Today,NE comes up with a new algorithm and names it Strange Sorting.
There are many rounds in Strange Sorting. For each round, NE chooses a number, and keeps swapping it with its next number while the next number is less than it. For example, if the sequence is “1 4 3 2 5”, and NE chooses “4”, he will get “1 3 2 4 5” after this round. Strange Sorting is similar to Bubble sort, but it’s a randomized algorithm because NE will choose a random number at the beginning of each round. NE wants to know that, for a given sequence, how many rounds are needed to sort this sequence in the best situation. In other words, you should answer the minimal number of rounds needed to sort the sequence into ascending order. To simplify the problem, NE promises that the sequence is a permutation of 1, 2, . . . , N .
翻译：
Nervending是一个ACMer。
昨天，NE学习了一种算法：冒泡排序。冒泡排序将比较每对相邻项目，如果顺序错误则将它们交换。重复该过程，直到不需要交换为止。
今天，NE提出了一种新算法，并将其命名为“奇怪排序”。
奇怪排序中有很多回合。对于每一轮，NE都会选择一个数字，并在下一个数字小于该数字时继续将其与下一个数字交换。例如，如果序列为“ 1 4 3 2 5”，而NE选择“ 4”，则在此回合后他将获得“ 1 3 2 4 5”。奇怪排序与气泡排序类似，但是它是一种随机算法，因为网元会在每个回合开始时选择一个随机数。 NE要知道，对于给定的序列，在最佳情况下需要多少轮才能对该序列进行排序。换句话说，您应该回答将序列按升序排序所需的最少轮数。为了简化问题，NE承诺序列是1、2，…的排列。 。 。 ，N。
Input
The first line contains only one integer T (T ≤ 200), which indicates the number of test cases. For each test case, the first line contains an integer N (1 ≤ N ≤ 106).
The second line contains N integers a i (1 ≤ ai ≤ N ), denoting the sequence NE gives you.
The sum of N in all test cases would not exceed 3 × 106.
Output
For each test case, output a single line “Case #x: y”, where x is the case number (starting from 1), y is the minimal number of rounds needed to sort the sequence.
Sample Input
2
5
5 4 3 2 1
5
5 1 2 3 4
Sample Output
Case #1: 4
Case #2: 1
三、题意拆解
- 首先，我们知道我们要做的是对计算一个排序的最小轮次，那么让我们看看题目大致给的内容：
对于每一轮，NE都会选择一个数字，并在下一个数字小于该数字时继续将其与下一个数字交换。例如，如果序列为“ 1 4 3 2 5”，而NE选择“ 4”，则在此回合后他将获得“ 1 3 2 4 5”。
- 这是什么意思呢？当我们选择了数字之后，这个数字会在这个轮次里一直与后面比他小的数字交换，以此使本轮次的这个数字保证它后面的数字比它大。
- 这里有个点要注意，仅仅是它的后面的数字比它大，而不是它后面所有数字。
- 好！我们接着看后面的题目：
奇怪排序与气泡排序类似，但是它是一种随机算法，因为网元会在每个回合开始时选择一个随机数。 NE要知道，对于给定的序列，在最佳情况下需要多少轮才能对该序列进行排序。换句话说，您应该回答将序列按升序排序所需的最少轮数。
- 这里题目的意思就很明显了。我们要找出一种选择数字的方法，使其成为一个升序序列同时轮次最小。
- 数据范围
T ≤ 200
1 ≤ N ≤ 106
数据和<=3 × 106
四、解题思路
- 现在，让我们来试着分析下题目中“奇怪排序”的工作逻辑：
- 随机选择一个数字
- 使其“下沉”，直到遇到比它大的数字。
- 重复1-2步，直到该序列成为一个升序序列。
- 那么，怎么样才能让这个轮次最少呢？
很简单，我们每轮选择的都是数组中最大的元素，那么，即使是最多次的轮次，也只是n次 - 那么这个最少轮次我们又需要怎么计算呢？
首先，我们需要判断数组中有哪些数是需要“下沉”的，找出这些数字的数量，就是我们需要的最少轮次。那么这些数字的数量我们应该怎么去找？ - 一个数字在数组中需要“下沉”的原因是什么？是在它的下方有比它“轻”的数字，那么我们只需要看看哪些数的下方有比它“轻”的数字就可以了。
具体思路 - 从数组最后一位遍历到数组头，记录下数组重当前位置的最小数字，当目前的数字比最小数字大，就让轮次+1。
- 如：
5 4 3 1 2
我们定义一个轮次sum，初始化为0.定义一个数组当前最小数min，使其等于数组最后一位数字，然后从数组倒数第二位开始由后向前遍历。 - i = 1，扫描到1，min=2<1，min更新，此时min=1，sum=0
- i = 2，扫描到3，min=1>3，该数字需要下沉，sum++，min不变，此时数组排序为 5 4 1 2 3
- i = 3，扫描到4，min=1>4，数字下沉，sum++
- i=4，扫描到5，min>5，数字下沉，sum++
- 输出结果sum=3
五、代码
#include "iostream"
using namespace std;
int main()
{
int n;
scanf("%d",&n);//输入样例数
for(int i=1;i<=n;i++)
{
int t;//数组大小
scanf("%d",&t);
int a[t+5];
for(int g=0;g<t;g++)
{
scanf("%d",&a[g]);//用scanf可以防止数据过多超时
}
int sum=0;//定义轮次
int mnum=a[t-1];//定义当前最小数字，使其等于数组末尾数字
for(int g=t-2;g>=0;g--)
{
if(a[g]>mnum)//如果当前数字大于最小数字，说明数字需要下沉
{
sum++;
} else//如果不需要下沉，更新最小数
{
mnum=a[g];
}
}
printf("Case #%d: %d\n",i,sum);
}
}
- 需要注意的点是用cin不同时外挂个
ios::sync_with_stdio(false);
- 的话会超时，所以推荐用scanf输入数据。