本文共 2496 字，大约阅读时间需要 8 分钟。
这两天比赛思维题比较多，算法设计的比较少，今天看了矩阵快速幂的内容，刷了几道以前比赛没做出来的思维题，今晚的比赛的A题感觉是道水题，但在当时没做出来。
赛后网上找了大佬的思路，很是清晰。
B. Unsorting Array
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Little Petya likes arrays of integers a lot. Recently his mother has presented him one such array consisting of n elements. Petya is now wondering whether he can swap any two distinct integers in the array so that the array got unsorted. Please note that Petya can not swap equal integers even if they are in distinct positions in the array. Also note that Petya must swap some two integers even if the original array meets all requirements.
Array a (the array elements are indexed from 1) consisting of n elements is called sorted if it meets at least one of the following two conditions:
Help Petya find the two required positions to swap or else say that they do not exist.
Input
The first line contains a single integer n (1 ≤ n ≤ 105). The second line contains n non-negative space-separated integers a1, a2, ..., an — the elements of the array that Petya's mother presented him. All integers in the input do not exceed 109.
Output
If there is a pair of positions that make the array unsorted if swapped, then print the numbers of these positions separated by a space. If there are several pairs of positions, print any of them. If such pair does not exist, print -1. The positions in the array are numbered with integers from 1 to n.
Examples
input
Copy
11
output
Copy
-1
input
Copy
21 2
output
Copy
-1
input
Copy
41 2 3 4
output
Copy
1 2
input
Copy
31 1 1
output
Copy
-1
Note
In the first two samples the required pairs obviously don't exist.
In the third sample you can swap the first two elements. After that the array will look like this: 2 1 3 4. This array is unsorted.
大致题意为：
给出一个单调的序列，减缓两个不同的数，使它不单调。
直接暴力即可。
#include#include #include using namespace std;int a[100005],a1[100005],a2[100005];bool cmp(int x,int y){ return x>y;}int check(int *ch_a,int *ch_aa,int nn){ for(int i=1;i<=nn;i++) { if(ch_a[i]!=ch_aa[i]) return 0; } return 1;}int main(){ int n; while(cin>>n) { for(int i=1;i<=n;i++) { cin>>a[i]; a1[i]=a[i]; a2[i]=a[i]; } sort(a1+1,a1+n+1); sort(a2+1,a2+n+1,cmp); int ch1=check(a,a1,n),ch2=check(a,a2,n); int t,ok=0; if(ch1==1&&ch2==1) { cout<<"-1"<
转载地址：http://ymyzi.baihongyu.com/