共有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张修改劵。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)