首页 > 代码库 > CodeForces 451B (翻转一次递减子序列得到递增序列) 简单题

CodeForces 451B (翻转一次递减子序列得到递增序列) 简单题

题目大意:判断能否找到递减的子列,将其翻转后得到的整个数列递增,只能找一次,最后输出,如果能还要输出翻转的首尾位

                    置,注意数数组下标,不是首尾的数,当然如果本来数列就递增,就随便找个数翻一下。

        我的方法是直接模拟,直接从a[0]开始寻找递减序列,然后判断递减序列翻转后能否构成递增序列。

#include<stdio.h>
int n,a[100005];
int main()
{
    int i,j,h;
      bool bo=true;
        scanf("%d",&n);
          for (i=0;i<n;i++)scanf("%d",&a[i]);
            i=0;
    while (a[i]<=a[i+1]&&i<n-1) i++;   //找到开始递减的数a[i],即左端点
      if (i==n-1)      //如果数列一直递增,就省事多了
        {
           bo=false;
           printf("yes\n1 1");
        }
           j=i;
    while (j<n-1&&a[j]>a[j+1]&&bo) j++;      //找到递减序列的右端点
           if (i>0&&a[j]<a[i-1]&&bo)         //看看能不能接上,就是递减子列翻转后的左端点不能小于前一个数
           {
               printf("no\n");
               bo=false;
           }
    if (j==n-1&&bo)                                //判断后面是否还有数
        {
            bo=false;
            printf("yes\n%d %d\n",i+1,j+1);
        }
           h=j;
           if (h<n-1&&a[h+1]<a[i]&&bo)        //看看能不能接上
           {
               printf("no\n");
               bo=false;
           }
    while (h<n-1&&bo)          //如果后面还有数有,看看能不能保证递增
    {
        if (a[h]>a[h+1])
        {
            bo=false;
            printf("no\n");
        }
        h++;
    }
    if (bo) printf("yes\n%d %d\n",i+1,j+1);         
    return 0;
}

         我的方法有点啰嗦,实际上还有方法,就是现将整个数列按由小到大排序后与原数列比较,

在原数列中分别从最左端、最右端开始找不相等的数,看看这段子列是否满足递减。

推荐使用先排序、后比较的方法。