524
cf 153.div2 B. Unsorting Array
最近寫題目越來越少了，以至於這種簡單題都會錯……比賽的時候寫了個n^2的算法，果斷超時，賽後加了個剪枝，78ms
但是其實因為隻要把有序序列中的連續不相等的兩項交換，即可使之無序……所以o(n)就夠了
o(n^2)
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define INF 1E9
using namespace std;
int a[100005],b[100005],c[100005];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
int n;
scanf("%d",&n);
if(n<=2){cout<<-1<<endl;return 0;}
int j,i;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
b[i]=c[i]=a[i];
}
sort(b,b+n);
if(b[0]==b[n-1]){cout<<-1<<endl;return 0;}
sort(c,c+n,cmp);
for(i=0;i<n;i++)
{
if(a[i]==a[i+1])continue;
for(j=i+1;j<n;j++)
{
if(a[j]==a[j-1])continue;
if(a[i]==a[j])continue;
if((a[j]!=b[i]||a[i]!=b[j])&&(a[i]!=c[j]||a[j]!=c[i]))
{
cout<<i+1<<" "<<j+1<<endl;
return 0;
}
}
}
cout<<-1<<endl;
return 0;
}
o(n)
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
int f[111111],n,i;
main()
{
scanf("%d",&n);
for(i=1; i<=n; i++)scanf("%d",&f[i]);
for(i=2; i<=n; i++)if(f[i] != f[i-1])
{
swap(f[i],f[i-1]);
bool ok1 = true,ok2 = true;
for(int j=2; j<=n; j++)
{
if(f[j-1]>f[j])ok1 = false;
if(f[j-1]<f[j])ok2 = false;
if(ok1 || ok2)continue;
printf("%d %d",i-1,i);
return 0;
}
swap(f[i],f[i-1]);
}
puts("-1");
return 0;
}
最後更新：2017-04-02 00:06:51