阿里笔试（2021.3.19）

阿里笔试（2021.3.19）

共有n人，每人开始抽一个初始序号a[]。如果某人的序号是某个数的平方，那他就会获奖。现在会发放一些数量的修改券，使用一张修改券可以使自己的序号加一或减一。现在想知道，如果想要让一半人可以获奖，至少要发放多少张修改券?

输入
4
4 7 12 13
输出
2

public class Solution {
    public int integerReplacement(int num) {
        int left = (int) Math.sqrt(num);
        int right = left + 1;
        int num1 = Math.abs(num - left * left);
        int num2 = Math.abs(num - right * right);
        return Math.min(num1, num2);
    }
    
    public int returnRes(int nums[]) {
        int numsTemp[] = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numsTemp[i] = integerReplacement(nums[i]);
        }
        Arrays.sort(numsTemp);
        int res = 0;
        for (int i = 0; i < numsTemp.length / 2; i++) {
            res += numsTemp[i];
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int num[] = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = scanner.nextInt();
        }
        System.out.println(new Solution().returnRes(num));
    }

}

思路（欢迎指正）
就是求每个a[i]最少的修改劵，只要是平方就获奖。对于本身就是某个数平方的数，使用0张修改劵，对于本身不是某个数平方的数，通过修改劵到离其最近的某个数平方的数。例如8，离它最近就是9，所以使用1张修改劵。