首页 > 代码库 > 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; }
我的方法有点啰嗦,实际上还有方法,就是现将整个数列按由小到大排序后与原数列比较,
在原数列中分别从最左端、最右端开始找不相等的数,看看这段子列是否满足递减。
推荐使用先排序、后比较的方法。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。