题目大致是这样的:
第一行输入N,X(N为数组长度,X为等差数列的公差,X大于0);第二行输入为N个正整数,代表数组元素。每次可以变化数组中的一个元素为任意正整数,问将数组变成一个以X为公差的等差数列最小的步数(数列为正整数数列)。
本地用了几个测试用例均通过,但是提交上去AC只有0.18,提示答案错误(没有超时超空间)请大佬指正:
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int x=sc.nextInt();
int[] trees=new int[n];
for(int i=0;i<n;i++){
trees[i]=sc.nextInt();
}
sc.close();
int length=0; //连续等差子列长度
int max=0; //记录最长的长度
for(int i=1;i<n;i++){
if(trees[i]-trees[i-1]==x&&trees[i-1]>=1+(i-1)*x){ //寻找连续等差子数列,且该子序列起始点的值需满足让变化后的tree[0]>=1
length++;
max= max>length?max:length; //更新max
}else{ //不满足条件则length归零
length=0;
}
}
System.out.println(n-max-1);
}
}
全部评论
(3) 回帖