MYF

Codeforces 252B Unsorting Array

Posted on | In | | Visitors

题目链接

codeforces 252B

解题方法：贪心

题目分析

题目大意

给n个数字，这n个数字可以交换任意两个不相等的数字一次，问是否能形成一个非排序数列。也就是说，在交换完的数列中，存在三个数字a、b、c，使a<b且b>c 或者 a>b且b<c

解析

两种方法：分别对应下面两种代码。

方法一：

先正序扫一遍数组，找两组数一组a<b，一组a<c，且a的下标小于b的下标小于c的下标，交换a、b的值，则必有a>b且b<c。同时，找两组数一组a>b，一组a>c，且b的下标小于c的下标，交换a、b的值，则必有a<b且b>c。

再倒叙扫一遍数组，找两组数一组a<b，一组a<c，且a的下标大于b的下标大于c的下标，交换a、b的值，则必有a>b且b<c。同时，找两组数一组a>b，一组a>c，且b的下标大于c的下标，交换a、b的值，则必有a<b且b>c。

注：本方法参考acing.cf

方法二：
先把给的数字排序，生成一个上升序列，一个下降序列。也就是说，只要不是这两个序列，就是我们目标的unsorting array。

先排除特殊情况：

  1. 一开始给的数列a，既是上升序，又是下降序。
  2. 总共就俩数。

    暴力枚举，将每两个位置的数字交换，看看交换之后是否会和上升序列或者下降序列之一完全相同，如果完全相同则枚举下一个位置如果没有结果，则输出-1。

    函数解释：check()函数，检查该序列是否和a相同。这个函数还是比较巧妙的，每交换一次，要判断交换完的a[]和asc[]比较，再判断交换完的a[]和dsc[]比较，既然都和a比较，干脆就写一个和a比较的函数，用不动数组和变动数组比较。

代码

方法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=100050;
int a[maxn]= {};
int main()
{
    set<int>st;
    int n;

    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d",a+i);
        st.insert(a[i]);
    }

    if(st.size()==1||n<3)
    {
        printf("-1\n");
        return 0;
    }

    for(int i=0; i<n; i++)
    {
        int id1=-1,id2=-1;
        for(int j=i+1; j<n; j++)
        {
            if(id1!=-1&&a[i]>a[j])
            {
                printf("%d %d\n",min(id1+1,i+1),max(id1+1,i+1));
                return 0;
            }

            if(id2!=-1&&a[i]<a[j])
            {
                printf("%d %d\n",min(id2+1,i+1),max(id2+1,i+1));
                return 0;
            }

            if(a[i]>a[j]) id1=j;
            if(a[i]<a[j]) id2=j;
        }
        while (i<n-1&&a[i]==a[i+1]) i++;
    }

    for(int i=n-1; i>=0; i--)
    {
        int id1=-1,id2=-1;
        for(int j=i-1; j>=0; j--)
        {
            if(id1!=-1&&a[j]>a[i])
            {
                printf("%d %d\n",min(id1+1,i+1),max(id1+1,i+1));
                return 0;
            }
            if(id2!=-1&&a[i]>a[j])
            {
                printf("%d %d\n",min(id2+1,i+1),max(id2+1,i+1));
                return 0;
            }
            if(a[j]>a[i]) id1=j;
            if(a[i]>a[j]) id2=j;
        }
        while (i-1>=0 &&a[i]==a[i-1]) i--;
    }
    printf("-1\n");
    return 0;
}

方法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=100050;
int n;
int a[maxn]= {};
int asc[maxn]={};
int dsc[maxn]={};
//判断数组num与数组a是否相等
bool check(int *num){
    for(int i=1;i<=n;i++)
        if(a[i]!=num[i]) return false;
    return true;
}
bool cmp(int x,int y){
    return x>y;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        asc[i]=a[i];
        dsc[i]=a[i];
    }
    sort(asc+1,asc+n+1);
    sort(dsc+1,dsc+n+1,cmp);

    if(n<3||(check(asc)&&check(dsc))){
        printf("-1\n");
        return 0;
    }

    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(a[i]!=a[j]){
                swap(a[i],a[j]);
                if(!check(asc)&&!check(dsc)){
                    printf("%d %d\n",i,j);
                    return 0;
                }
                swap(a[i],a[j]);
            }
        }
    }
    printf("-1\n");
    return 0;
}