#人寿研发中心笔试# 笔试第三题标答是不是有问题啊,题目大意是给定一串整数序列,选择一种最少的划分使得每一段都是某个公差大于1的等差序列的子序列。
样例
7
1 5 11 2 6 4 7
输出
3
最少的划分是
1 5 11,2 6 4,7 这样子
但是我测试了
3
1 2 4
标答居然输出3,不应该是2么,1,2 4
我的想法是首先这是一个贪心的结构,能多加一个数就多加一个数
其次容易证明一段序列是一个公差大于1的等差序列的子序列 当且仅当 其差分序列的最大公约数大于1
全部评论

相关推荐

评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务