Zookeeper使用 HTML框架 Synchnorized properties Java Out Of Memory android教程 gitee reactjs lambda path null jquery使用ajax eclipse闪退 cad怎么重复上一次命令 oracle行转列函数 python手册 python创建txt文件并写入 python开发 python零基础 java继承 java抽象 java表达式 怎么安装linux 远程登录linux java游戏开发 信息系统项目管理师教程 火牛软件 房产证生成器 js闭包的理解 路由器有没有辐射 js数组移除指定元素 谷歌地球用不了 ip地址转换器 c程序 贪吃蛇c语言代码 dns劫持怎么解决 3dmax材质编辑器 浣海之核 ps阵列 浏览器安卓
当前位置: 首页 > 学习教程  > 编程语言

最少的操作次数,构造等差数列,每次可以对一个数进行+1或者-1操作

2020/8/31 14:37:00 文章标签:

思路:由等差数列An = An-1 + d
我们只需要找出 d 即可,
我们对数组进行排序,前面两个数可以+1,-1,不变有3*3=9种
只需要找出其中需要操作次数最少的一种即可

import java.util.*;

public class Q2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i ++) {
            int n = sc.nextInt();
            int [] a = new int[n];

            for (int j = 0; j < n; j ++) {
                a[j] = sc.nextInt();
            }

            int res = getCount(a);
            System.out.println(res);
        }
        sc.close();
    }
    //每次可以对一个数进行+1, - 1操作
    //最少多少次使数列变成等差数列
    //1 5 6 7-->3
    public static int getCount(int[] a) {
        if (a == null || a.length <= 2) {
            return 0;
        }
        Arrays.sort(a);//排序

        int ans = Integer.MAX_VALUE;

        for (int i = -1; i <= 1; i ++) {
            for (int j = -1; j <= 1; j++) {
                int first = a[0] + i;//第一项
                int second = a[1] + j;//第二项

                int delta = second - first;//等差
                int cur = second;//进行比较

                int count = 0;
                for (int x = 2; x < a.length; x ++) {
                    cur += delta;//加上等差与下一项比较
                    if (Math.abs(cur - a[x]) <= 1) {//差值的绝对值在1之内,可以
                        count += Math.abs(cur - a[x]);
                    } else {
                        break;//否则不行
                    }

                    if (x == a.length - 1) {
                        ans = Math.min(count, ans);
                    }
                }
            }
        }

        return ans;
    }
}


本文链接: http://www.dtmao.cc/news_show_150268.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?