题目链接:http://120.78.162.102/problem.php?id=6241
时间限制: 1 Sec  内存限制: 128 MB

题目描述

给一个 1 到 n 的排列，每次可以交换相邻两个数，问使用最少操作次数使得序列递增的方案是否唯一。 

输入

多组输入，每组一个数n（1<=n<=10^5），然后是一个1~n的排列。

输出

方案唯一输出Yes，否则输出No。

样例输入

1
2
2 1
3
3 2 1

样例输出

Yes
Yes
No

解题思路

首先判断相邻的的非递增的有几个，如果有1个，那么从判断一下前向后判断交换或从后往前判断交换是否一遍就行，如果一遍都不行，证明不唯一。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a[100010], b[100010];
int main()
{
    int t, n, m, q;
    while (~scanf("%d", &n))
    {
        t = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            b[i] = a[i];
            if (i != 1 && a[i] < a[i - 1])
                t++;
        }
        if(t < 2)
        {
            if (t)
            {
                for (int i = 2; i <= n; i++)
                    if (a[i] < a[i - 1])
                        swap(a[i], a[i - 1]);
                for (int i = 2; i <= n && t; i++)
                    if (a[i] < a[i - 1])
                        t = 0;
                q = 1;
                for (int i = n; i >= 2; i--)
                    if (b[i] < b[i - 1])
                        swap(b[i], b[i - 1]);
                for (int i = 2; i <= n && q; i++)
                    if (b[i] < b[i - 1])
                        q = 0;
                if (t || q)
                    cout << "Yes" << endl;
                else cout << "No" << endl;
            }
            else cout << "Yes" << endl;
        }
        else cout << "No" << endl;
    }
    return 0;
}