第 338 场周赛 （力扣周赛）_质数减法运算

6354. K件物品的最大和

袋子中装有一些物品，每个物品上都标记着数字 1 、0 或 -1 。

给你四个非负整数 numOnes 、numZeros 、numNegOnes 和 k 。

袋子最初包含：

numOnes 件标记为 1 的物品。
numZeroes 件标记为 0 的物品。
numNegOnes 件标记为 -1 的物品。
1
2
3

现计划从这些物品中恰好选出 k 件物品。返回所有可行方案中，物品上所标记数字之和的最大值。

---

思路： 贪心的一个思路，先找大的去拿，即1 ， 0 ， -1.
code

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

6355.质数减法运算

给你一个下标从 0 开始的整数数组 nums ，数组长度为 n 。

你可以执行无限次下述运算：

选择一个之前未选过的下标 i ，并选择一个 严格小于 nums[i] 的质数 p ，从 nums[i] 中减去 p 。

如果你能通过上述运算使得 nums 成为严格递增数组，则返回 true ；否则返回 false ;
严格递增数组 中的每个元素都严格大于其前面的元素。

示例：
输入：nums = [4,9,6,10]
输出：true
解释：
在第一次运算中：选择 i = 0 和 p = 3 ，然后从 nums[0] 减去 3 ，nums 变为 [1,9,6,10] 。
在第二次运算中：选择 i = 1 和 p = 7 ，然后从 nums[1] 减去 7 ，nums 变为 [1,2,6,10] 。
第二次运算后，nums 按严格递增顺序排序，因此答案为 true 。

---

思路： 看数据范围，先把1000以内的质数全部找出来，然后我们进行思考，因为想要维持一个绝对递增的一个序列，如果我们从后往前，那么序列应该前一个总是小于后一个。

如果遇见不小于的呢？我们应该让前面这个数减去尽可能小的质数，因为减去尽可能小的满足题意的质数才能使得前面还没有遍历的数有更多的选择余地。

如此遍历一遍，然后再次遍历确定数组是否为一个递增数组即可。

code

class Solution {
public:
	int z[168] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
    bool primeSubOperation(vector<int>& nums) {
         int n = nums.size();
         if(n == 1) return true;
         //从后往前遍历，看到哪里不通顺了
         bool flag = 0;
		 for(int i=n-1;i>=1;i--){
		 	if(nums[i] > nums[i-1]){
		 		  continue;	
			}
			else{
				int res = nums[i-1] - nums[i];//看看大多少,让他减去一个较小的值 
				int pos;
				for(int j=0;j<168;j++){
					if(z[j] > res ){
						if(z[j] < nums[i-1]){
							nums[i-1] -= z[j];
						    break;
						}
					}
				} 
			}
		 }
		 
		 for(int i=1;i<n;i++){
		 	if(nums[i] <= nums[i-1]){
		 		flag  = 1;
		 		break;
			 }
		 }
		 if(flag) return false;
		 else return true; 
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

---

6357.使数组元素全部相等的最少操作次数

给你一个正整数数组 nums 。

同时给你一个长度为 m 的整数数组 queries 。第 i 个查询中，你需要将 nums 中所有元素变成 queries[i] 。你可以执行以下操作 任意 次：

将数组里一个元素 增大 或者 减小 1 。

请你返回一个长度为 m 的数组 answer ，其中 answer[i]是将 nums 中所有元素变成 queries[i] 的 最少 操作次数。

注意，每次查询后，数组变回最开始的值。

示例：
输入：nums = [3,1,6,8], queries = [1,5]
输出：[14,10]
解释：第一个查询，我们可以执行以下操作：

• 将 nums[0] 减小 2 次，nums = [1,1,6,8] 。
• 将 nums[2] 减小 5 次，nums = [1,1,1,8] 。
• 将 nums[3] 减小 7 次，nums = [1,1,1,1] 。
  第一个查询的总操作次数为 2 + 5 + 7 = 14 。
  第二个查询，我们可以执行以下操作：
• 将 nums[0] 增大 2 次，nums = [5,1,6,8] 。
• 将 nums[1] 增大 4 次，nums = [5,5,6,8] 。
• 将 nums[2] 减小 1 次，nums = [5,5,5,8] 。
• 将 nums[3] 减小 3 次，nums = [5,5,5,5] 。
  第二个查询的总操作次数为 2 + 4 + 1 + 3 = 10 。

---

思路： 其实对于每一个queries[i]，无非是三种选择：

• nums数组每一个数字都大于queries[i]，这个时候全部进行减操作。操作次数即nums数组总和 - nums数组长度 * queries[i]。
• nums数组每一个数字都小于queries[i]，这个时候全部进行加操作。操作次数即nums数组长度 * queries[i] - nums数组总和。
• 有大于有小于，这个时候我们需要对num进行排序，随后分情况分别计算。

因为数据范围比较大，暴力肯定会T，所以我们这里选择使用前缀和与二分法来进行优化。

code

class Solution {
public:
	vector<long long> ans;
	//long long f[100010];
    vector<long long> f;
    vector<long long> minOperations(vector<int>& nums, vector<int>& queries) {
        long long  l = nums.size();
        long long ll = queries.size();
        long long res=0;
        long long pos;
        
        if(l == 1){
        	for(int i=0;i<ll;i++){
        		res = abs(queries[i] - nums[0]);
        			ans.push_back(res); 
			}
		}
		else{
			 //每次无非是减小或者增大
        sort(nums.begin(),nums.end());
        
        //前缀和
		//f[0] = nums[0];
        f.push_back(nums[0]);
		for(int i=1;i<l;i++){
			pos = f[i-1] + nums[i];
            f.push_back(pos);
		}
        
		for(int i=0;i<ll;i++){
			res = 0;
			pos = queries[i];
			if(lower_bound(nums.begin(),nums.end(),pos)!=nums.end()){
				int k = lower_bound(nums.begin(),nums.end(),pos) - nums.begin();//第一个大于等于的位置
				//cout<<"k = "<<k<<endl;
				if(k == 0){
					res += (f[l-1] - pos*l);
				} 
				else{
					res += (pos * (k) - f[k-1]);//前面都比其小
				//	cout<<"res = "<<res<<endl;
					res += ((f[l-1] - f[k-1]) - pos*(l-k)); 
//					cout<<"111111 = "<<(f[l-1] - f[k-1])<<endl;
//					cout<<"22222 == "<<pos*(l-k+1)<<endl;
//					cout<<"res = "<<res<<endl;
				}
			}
			else{
				res += (pos*l - f[l-1]);//说明都比这个数小 
			}
			ans.push_back(res); 
		}
			
		}
       
		return ans;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

6356. 收集树中金币

W了，待补~