有效凸数组两道题

题目一

给定一个长度为len的整数数组 arr,如果它是有效的凸数组就打印输出字符串"true",否则打印输出"false"。

如果数组arr 满足下述条件,那么它是一个有效的凸数组:

  • len >= 3
  • 在 0 < i < len - 1 条件下,存在 i 使得:
    arr[0] < arr[1] < ... arr[i-1] < arr[i]
    arr[i] > arr[i+1] > ... > arr[len - 1]

有效凸数组图示如下:

有效凸数组两道题

样例1

输入

arr = [2,1]

输出

false

 运用单指针方法

有效凸数组两道题

 

题目二

输入一个长度为len的数组a和一个整数peak,你需要将数组a构造成一个最大值下标等于peak的有效凸数组,你需要打印出该有效凸数组。下面对构造完成的有效凸数组做进一步的限制,要求构造的有效凸数组至少包含一个等腰三角区或直角三角区(当peak=len-1或者peak=0时有效凸数组不含有等腰三角区)。

  • 等腰三角区底边中线元素为数组最大值,下标为peak。要求等腰三角区内的数组元素满足
    a[peak]>=a[peak-1]>=a[peak+1]>=a[peak-2]>=a[peak+2]....
  • 直角三角区内的所有元素小于或等于等腰三角区的最小元素。
  • 直角三角区内的元素有序,且大值的下标(相比于小值)更接近peak。

有效凸数组两道题

输出描述

输出完成构造的有效凸数组。

#include<stdio.h>

int main(){
    int len,peak,num,a[10001]={},b[10001]={},s;
    scanf("%d %d",&len,&peak);
    for(int i=1;i<=len;i++){//
        scanf("%d",&a[i]);
    }
    for(int i=1;i<len;i++){
        for(int j=i+1;j<=len;j++){
            if(a[i]>a[j]){
                a[i]^=a[j];
                a[j]^=a[i];
                a[i]^=a[j];
            }
        }
    }
    int cn=len;
    b[peak]=a[cn--];
    for(s=1; peak+s<len && peak-s>=0 ;s++){
        b[peak-s]=a[cn--];
        b[peak+s]=a[cn--];
    }
    //如果m-s<0会跳出,这时就知道右边其实更长 
    if(peak-s>=0) for(;peak-s>=0;s++) b[peak-s]=a[cn--];
    else for(;peak+s<len;s++) b[peak+s]=a[cn--];
    for(int i=0;i<len;i++){
        printf("%d ",b[i]);
    }
}

心得

这题卡人的地方就是怎么找到peak两边配套的数,怎么把剩余的空位根据peak的位置补上数。

其实只要使用一个s=1 用 s++,peak-s>=0 && m+s<n,让计算机判断,如果peak-s<0,则说明右边更长;如果peak+s》n,则说明左边更长,然后依据相同的循环条件赋值到底。

上一篇:HTML在网页上不能显示图片问题


下一篇:放学(YZOJ-1029)