C语言实践第二次习题集之美丽数组(贪心典型)

美丽数组

题目

小明是个普通的计算机本科生,很喜欢研究数组相关的问题。在他的认知里,美丽的数组是这样的,对于一个长度为n的数组a,存在一个下标i(1<=i<=n)使得1~i之间的数是严格递增的,i+1~n之间的数是严格递减的。现在这个数组a里的元素是随机给定的(这个数组可能是不美丽的),对于数组a内的任意一个元素ai我们可以进行若干次ai=ai-1(ai>0)的操作,问能否通过若干次操作使得这个数组变得美丽。

输入格式:

第一行输入数组长度n (1≤n≤3*1e5), 第二行输入n个整数a1,…,an (0≤ai≤1e9)。

输出格式:

输出“Yes”表示这个数组可以变美丽,输出“No”表示不可以。

输入样例:

3
1 0 1

输出样例:

No

思路

这题是典型的贪心算法题。贪心算法的做法即是局部取最优解,最终使整体也能达到最优解。因此,此题要研究数组下标中是否存在某个i,使i前的数组单调递增,i后的数组单调递减。于是,利用贪心的思

想,应该从数组前后同时向数组中间逼近,在逼近过程中不断检查元素是否可以通过进行若干次ai=ai-1(ai>0)的操作使其变为最优解(当前位置所能取得的最小值(即若为最边缘的两个元素(i=0,j=n-1),取0,否则,a[i]=a[i-1]+1,a[j]=a[j+1]+1),若无法,则说明符合题目要求的i不存在,若可以,则继续检查,继续

由两边向数组中间逼近。

完整代码如下

#include<stdio.h>
int judge1(int i);
int judge2(int j);
int a[300005],n;
int main()
{
    int i,j,flag=1;
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&a[i]);
    i=0;
    j=n-1;
    while(i<=j&&flag==1){
        if(i==j){//这里要注意i和j相等时,需要写一个特判 
            if(a[i]<=a[i-1]&&a[i]<=a[i+1]) flag=0;//此时最中间的这个元素不能同时小于相邻的两个元素 
        }
        else{
            if(judge1(i)==1&&judge2(j)==1) ;
            else flag=0;
        }
        i++;
        j--;
    }
    if(flag==1&&n>2) printf("Yes");//不足三个元素的数组就无须考虑了,但pta好像没有在这点设置测试数据 
    else printf("No");
    return 0;
}
int judge1(int i)
{
    if(i==0){
        if(a[0]<=1) return 1;
        else{
            a[0]=1;
            return 1;
        }
    }
    else{
        if(a[i]>a[i-1]){
            a[i]=a[i-1]+1;
            return 1;
        }
        else return 0;
    }
}
int judge2(int j)
{
    if(j==n-1){
        if(a[j]<=1) return 1;
        else{
            a[j]=1;
            return 1;
        }
    }
    else{
        if(a[j]>a[j+1]){
            a[j]=a[j+1]+1;
            return 1;
        }
        else return 0;
    }
}