2555. 两个线段获得的最多奖品

题目

image-20240911152823095

解法

实际这道题目是动态规划的思想，最开始自己写的思路是找出一个线段的最大值再去在剩下的不重合区间内寻找下一个线段的最大值，但是这种情况下二者的 和 （最终的结果）不一定是最大的，前期的思路准备很重要

代码

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
int Array::maximizeWin(vector<int>& prizePositions, int k)
{
     int n = prizePositions.size();

   //对解雇是整个数组长度的情况提前进行解决
   //使用 k *2 + 1 是考虑到数组长度是偶数的时候，,同时> 的使用也把原本的奇数包括进去
	if (k * 2 + 1 >= prizePositions[n - 1] - prizePositions[0]) {
		return n;
	}
    
    
	int ans = 0, mx = 0, left = 0, right = 0;
    
    //并同时在这下边提出对于线段的遍历要从右侧的线段开始，不然会则 mx+right−mid 可能会把 mid 处的奖品计入两次。
	for (int mid = 0; mid < n; mid++) {
		// 把 prizePositions[mid] 视作第二条线段的左端点，计算第二条线段可以覆盖的最大奖品下标
		while (right < n && prizePositions[right] - prizePositions[mid] <= k) {
			right++;
		}
		// 循环结束后，right-1 是第二条线段可以覆盖的最大奖品下标
		ans = max(ans, mx + right - mid);
		// 把 prizePositions[mid] 视作第一条线段的右端点，计算第一条线段可以覆盖的最小奖品下标
		while (prizePositions[mid] - prizePositions[left] > k) {
			left++;
		}
		// 循环结束后，left 是第一条线段可以覆盖的最小奖品下标
		mx = max(mx, mid - left + 1);
	}
	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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
int Array::maximizeWin(vector<int>& prizePositions, int k)
{
	//两条线段可能会重合，找出最大值，线段B就需要严格在线段A外求解一个最长长度
	int n = prizePositions.size();
 
	int left1 = 0, right1 = 0; //线段A
	int max1 = 0;
	int indexl = 0, indexr = 0;
	while (right1 != prizePositions.size())
	{
		if (prizePositions[right1] - prizePositions[left1] <= k)
		{
			++right1;
		}
		else
		{
			++left1;
			//这个条件下已经是大于k，因为本身就需要在最后合适的结果上+1，就直接引用
			int temp = max(max1, right1 - left1 + 1);
			if (temp != max1)
			{
				indexl = left1 - 1;
				indexr = right1 - 1;
			}
 
			max1 = temp;
		}
	}
 
	if (max1 == 0 && right1 - left1 != 0)
	{
		max1 = right1 - left1;
		indexl = left1;
		indexr = right1 - 1;
	}
 
	int max2 = 0;
	if (indexl > 0)
 
	{
		left1 = 0, right1 = 0;
		max2 = 1;
		while (right1 <= indexl)
		{
			if (prizePositions[right1] - prizePositions[left1] <= k)
			{
				++right1;
			}
			else
			{
				++left1;
				max2 = max(max2, right1 - left1 + 1);
			}
		}
	}
 
	if (max2 == 0 && right1 - left1 != 0)
	{
		max2 = right1 - left1;
	}
 
	int max3 = 0;
	if (indexr < n - 1)
	{
		left1 = indexr + 1, right1 = indexr + 1;
		max3 = 1;
		while (right1 <= n)
		{
			if (prizePositions[right1] - prizePositions[left1] <= k)
			{
				++right1;
			}
			else
			{
				++left1;
				max3 = max(max3, right1 - left1 + 1);
			}
		}
	}
 
	if (max3 == 0 && right1 - left1 != 0)
	{
		max3 = right1 - left1;
	}
 
	return max1 + max(max2, max3);
 
 
 
}