题目描述
牛牛刚学完排序,他准备拿n个数一展身手,但是他发现现实中的排序与课堂里的排序不一样
每次他只能对连续的n-1个数进行从小到大的排序
请问牛牛最少需要几次排序能将所有的数排成有序的
输入描述:
第一行先输入一个整数n (3 ≤ ≤ 50)
第二行输入n个整数范围在1到1000以内
输出描述:
输出一个整数
题目分析:
这道题只要考虑到几个方面,还是很简单的,首先进行判断,这些数是不是已经排列好的,如果排列好了就不用在进行排序了,输出0就好了,如果最大值在最大值的位置,或者最小值在最小值的位置(但两者不能同时成立)就输出1,如果最大值在最小值的位置,最小值在最大值的位置(两者同时成立)则输出3,剩下的输出2就好了。 自我感觉如果好好分析的话还是比较简单的。
#include <cstdio> #include <iostream> #include <string> #include <cstring> #include <cmath> using namespace std; int main () { int a[1005]; int n; cin >> n; for (int i=1;i<=n;i++) { cin >> a[i]; } int best=0,bad=1000; for (int i=1;i<=n;i++) { best=max(best,a[i]); bad=min(bad,a[i]); } bool s=true; for (int i=1;i<n;i++) { if(a[i]>a[i+1]) s=false; } if(s) { cout << "0" << endl; return 0; } if(best == a[n]||bad == a[1]) cout << "1" << endl; else if(best == a[1]&&bad == a[n])cout << "3" << endl; else cout << "2" << endl; return 0; }