力扣第 338 场周赛前三题题解

题目链接：https://leetcode.cn/contest/weekly-contest-338

# T1. K 件物品的最大和

题目链接：https://leetcode.cn/problems/k-items-with-the-maximum-sum/

# 思路

贪心，先取 1，再取 0，最后取 - 1 的物品

	public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
	if (numOnes + numZeros >= k) {
	return numOnes > k ? k : numOnes;
	} else {
	return numOnes - (k - numOnes - numZeros);
	}
	}

题目链接：https://leetcode.cn/problems/prime-subtraction-operation/

质数，是大于 1 的自然数，且它的因数只有 1 和它本身。一般判断质数的算法有两种，一种是利用定义判断，一种是用质数表，以下的 Java 的实现。

	// 求取 [0, r] 以内的质数算法
	public boolean[] prime(int r) {
	//false - 是质数
	//true - 不是质数
	boolean[] nonPrime = new boolean[r + 1];

	// Sieve of Eratosthenes algorithm
	nonPrime[1] = true;
	for (int i = 2; i * i <= r; i++) {
	for (int j = i * i; j <= r; j += i) {
	nonPrime[j] = true;
	}
	}

	return nonPrime;
	}

贪心 + 判断质数

从左到右遍历数组 nums，下标从 1 开始（一个元素肯定就是严格递增的），
- 若 nums[i-1] < nums[i] ，继续遍历
- 否则，从最右边选择第一个没有操作过的下边开始做质数减法，尽可能让被减的质数最大，具体看代码注释

	class Solution {
	public boolean primeSubOperation(int[] nums) {
	int n = nums.length;
	// 最右边未选择的下标
	int pre = 0;
	for (int i = 1; i < n; ++i) {
	if (nums[i] > nums[i - 1]) continue;
	// 从最左边开始减少
	while (pre < i) {
	//nums [pre] 从最小值开始枚举
	int k = pre == 0 ? 1 : nums[pre - 1] + 1;
	int min = Math.min(nums[pre], nums[pre + 1]);
	while (k < min && !isPrime(nums[pre] - k)) {
	++k;
	}
	//k 可以等于 nums [pre]，但是必须小于 nums [pre]
	if (k >= nums[pre + 1]) return false;
	nums[pre++] = k;
	}
	}

	return true;
	}

	private boolean isPrime(int k) {
	if (k < 2) return false;

	int q = (int) Math.sqrt(k);

	for (int i = 2; i <= q; ++i) {
	if (k % i == 0) return false;
	}
	return true;
	}
	}

也能用质数表实现快速判断质数

	class Solution {
	public boolean primeSubOperation(int[] nums) {
	int n = nums.length;
	// 建立质数表
	//true - 非质数
	//false - 质数
	boolean[] nonPrime = new boolean[1000];
	nonPrime[1] = true;
	for (int i = 2; i * i < 1000; ++i) {
	for (int j = i + i; j < 1000; j += i) {
	nonPrime[j] = true;
	}
	}

	// 最右边未选择的下标
	int pre = 0;
	for (int i = 1; i < n; ++i) {
	if (nums[i] > nums[i - 1]) continue;
	// 从最左边开始减少
	while (pre < i) {
	//nums [pre] 从最小值开始枚举
	int k = pre == 0 ? 1 : nums[pre - 1] + 1;
	int min = Math.min(nums[pre], nums[pre + 1]);
	while (k < min && nonPrime[nums[pre] - k]) {
	++k;
	}
	if (k >= nums[pre + 1]) return false;
	nums[pre++] = k;
	}
	}

	return true;
	}
	}

二分 + 前缀和

对 nums 进行排序
记录 nums 的前缀和数组 sum
枚举每一个 query ，二分查找 query 在 nums 中插入位置 k ，即：
- 对于 0<=i<=k-1 ，都有 nums[i]<=query
- 对于 k<=i<=n-1 ，都有 nums[i]>query
那么当前最少的操作数就是 k * q - sum[k - 1] + sum[n-1] - sum[k-1] - q * (n - k)

	class Solution {
	public List<Long> minOperations(int[] nums, int[] queries) {
	int n = nums.length;

	Arrays.sort(nums);

	long[] sum = new long[n];

	sum[0] = nums[0];
	for (int i = 1; i < n; ++i) {
	sum[i] = sum[i-1] + nums[i];
	}

	List<Long> ret = new ArrayList<>();
	for (int q : queries) {

	int k = binary(nums, q);
	// nums[0 ... k-1] <= q && nums[k ... n-1] > q

	if (k == 0) {
	ret.add(sum[n - 1] - (long) n * q);
	} else if (k == n) {
	ret.add((long) n * q - sum[n - 1]);
	} else {
	ret.add(((long)k * q - sum[k - 1]) + (sum[n-1] - sum[k-1] - (long) q * (n - k)));
	}
	}

	return ret;
	}

	private int binary(int[] nums, int target) {
	int l = 0;
	int r = nums.length;

	while (l < r) {
	int m = (l + r) / 2;
	if (nums[m] <= target) l = m + 1;
	else r = m;
	}

	return l;
	}
	}