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; } }