codeforces 27 C. Unordered Subsequence

Posted by 111qqz on Tuesday, December 29, 2015

TOC

http://codeforces.com/contest/27/problem/C 题意:给出一个序列,问是否存在一个disordered的子序列。。输出长度并输出组成子序列的下表(1..n)。如果有多组,输出任意一组。 disordered的意思是。。升序或者降序(不严格也可以)之外的情况。 思路: 首先我们可以知道,我们要找的子序列至少需要三个点。因为两个点怎么看都是有序的。而如果有k个点(k>3)组成的子序列存在。。那么机智得去掉其中一些点,可以只剩三个 ,同样满足题意。所以我们只需要找到三个点即可。如果把点以下标为横坐标,值为纵坐标花在坐标系上,就是找一个v型或者倒v型的三个点。

第二,我们可以将找三个点的问题转化成用第一个点+找两个点的问题。我们可以证明,如果解存在,那么包含第一个点的解也一定存在。我们可以用反证法证明,如果我们选了第1个点,然后从第2个点到第n个点。。我们找不到两个点与第一个点构成一个v型,那么整个序列一定是升序或者降序,无解,与前提矛盾。

**需要注意的,判断方向的时候我用了乘,可能会爆int,记得用long long **

/* ***********************************************
Author :111qqz
Created Time :2015年12月29日 星期二 19时36分55秒
File Name :code/cf/problem/27C.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
LL a[N];
int n;
int main()
{
    #ifndef  ONLINE_JUDGE 
//	freopen("code/in.txt","r",stdin);
  #endif
    cin>>n;
    for ( int i = 1 ; i <= n ; i++) cin>>a[i];

    bool ok = true;
    for ( int i = 2 ; i <= n-1  ;i++)
    {
        if ((a[i]-a[1])*(a[i+1]-a[i])<0) //注意long long 
        {
        ok = false;
        printf("3\n1 %d %d\n",i,i+1);
        break;
        }
    }
    if (ok)
    {
        puts("0");
    }

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}