Tag Archives: 贪心

LeetCode Wiggle Subsequence

LeetCode Wiggle Subsequence
A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.
For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.
Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.
Examples:

Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.
Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Input: [1,2,3,4,5,6,7,8,9]
Output: 2

Follow up:
Can you do it in O(n) time?


一个抖动序列是指第一个数比第二个数小,第二个数比第三个数大,第三个数比第四个数小...或者第一个数比第二个数大,后续类似的交替的大小关系。
现给定一个数组,要求数组中最长的抖动序列的长度。
首先可以用贪心的方法,每次我们选择数据的拐点(局部最大或最小值点)。比如下图中,第一选了A,后续一直是上升的趋势,则选择最大的D能获得更长的抖动序列长度。如果此时选较小的C的话,则下一个只能选H了,这样就漏了E和G。

贪心的代码如下:

class Solution {
public:
	int wiggleMaxLength(vector<int>& nums) {
		int n = nums.size();
		if (n < 2)return n;
		int ans = 1, i = 0, j = 1;
		bool up = false;
		while (j < n && nums[j] == nums[i])++j;
		if (nums[j] > nums[i])up = true;
		else up = false;
		while (j < n) {
			if (nums[j] > nums[i] && up) {
				++ans;
				up = false;
				while (j + 1 < n&&nums[j + 1] >= nums[j])++j;
			}
			else if (nums[j] < nums[i] && !up) {
				++ans;
				up = true;
				while (j + 1 < n&&nums[j + 1] <= nums[j])++j;
			}
			i = j++;
		}
		return ans;
	}
};

本代码提交AC,用时3MS。
还可以用动态规划的方法,假设up[i]表示第i个元素处于抖动序列的最后一个位置,且是上升的趋势时,前[0,i]的抖动子序列的最大长度。类似的,down[i]表示第i个元素处于抖动序列的最后一个位置,且是下降趋势时,前[0,i]的抖动子序列的最大长度。
则对于第i个元素,可以枚举所有i前面的元素j跳到i,如果nums[i]>nums[j],则i处于抖动序列的上升末尾,则从j到i构成的抖动序列中,j是处于下降趋势的,所以有up[i]=max(up[i],down[j]+1)。类似的,如果nums[i]<nums[j],则有down[i]=max(down[i],up[j]+1)。最后返回1+max(up[n-1],down[n-1])。
代码如下:

class Solution {
public:
	int wiggleMaxLength(vector<int>& nums) {
		int n = nums.size();
		if (n < 2)return n;
		vector<int> up(n, 0), down(n, 0);
		for (int i = 1; i < n; ++i) {
			for (int j = 0; j < i; ++j) {
				if (nums[i] > nums[j])up[i] = max(up[i], down[j] + 1);
				else if (nums[i] < nums[j])down[i] = max(down[i], up[j] + 1);
			}
		}
		return 1 + max(up[n - 1], down[n - 1]);
	}
};

本代码提交AC,用时6MS。
可以对上述代码优化。j无需枚举所有i前面的元素,而是i直接根据和前一个元素i-1的大小关系进行更新。如果nums[i]>nums[i-1],则i处于上升末端,所以i-1必须处于下降末端,有up[i]=down[i-1]+1,down[i]不变,即down[i]=down[i-1]。如果nums[i]<nums[i-1],则i处于下降末端,所以i-1必须处于上升末端,有down[i]=up[i-1]+1,up[i]不变,即up[i]=up[i-1]。如果nums[i]==nums[i-1],则up[i]和down[i]都不变,分别等于up[i-1]和down[i-1]。
为什么这里可以不用枚举所有i前面的元素了呢,因为上述三种情况中,只更新了该更新的,不能更新的情况都等于前一个元素的结果了,比如第一种情况更新了up[i],则down[i]保持了down[i-1]的值,所以后续如果要用到down[i-1]的值,也可以直接用down[i]的值了。
代码如下:

class Solution {
public:
	int wiggleMaxLength(vector<int>& nums) {
		int n = nums.size();
		if (n < 2)return n;
		vector<int> up(n, 0), down(n, 0);
		up[0] = down[0] = 1;
		for (int i = 1; i < n; ++i) {
			if (nums[i] > nums[i - 1]) {
				up[i] = down[i - 1] + 1;
				down[i] = down[i - 1];
			}
			else if (nums[i] < nums[i - 1]) {
				down[i] = up[i - 1] + 1;
				up[i] = up[i - 1];
			}
			else {
				up[i] = up[i - 1];
				down[i] = down[i - 1];
			}
		}
		return max(up[n - 1], down[n - 1]);
	}
};

本代码提交AC,用时3MS。
还可以对上述代码进行空间的优化,因为up[i]和down[i]都只用到了前一个结果up[i-1]和down[i-1],所以只需保留前一个结果就行,不需要两个数组。代码如下:

class Solution {
public:
	int wiggleMaxLength(vector<int>& nums) {
		int n = nums.size();
		if (n < 2)return n;
		int up = 1, down = 1;
		for (int i = 1; i < n; ++i) {
			if (nums[i] > nums[i - 1]) {
				up = down + 1;
			}
			else if (nums[i] < nums[i - 1]) {
				down = up + 1;
			}
		}
		return max(up, down);
	}
};

本代码提交AC,用时0MS,是效率最好的一种解法了。
参考:https://leetcode.com/articles/wiggle-subsequence/,完整介绍了所有方法。

LeetCode Non-overlapping Intervals

LeetCode Non-overlapping Intervals
Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note:

  1. You may assume the interval's end point is always bigger than its start point.
  2. Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.

Example 1:

Input: [ [1,2], [2,3], [3,4], [1,3] ]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [ [1,2], [1,2], [1,2] ]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

Input: [ [1,2], [2,3] ]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

给定一系列区间,问最少删除多少个区间能使得剩余区间没有重叠。区间[i,j]和[u,v]重叠是指u<j或者i<v,如果两个区间只是边界重叠比如j==u,则不算重叠。
我们可以使用贪心的策略求最多能保存多少个区间,然后用总数一减就得到最少删除的区间数。
首先对区间先后按start和end从小到大排序,然后从头开始遍历。假设我们上一次保留的区间的end是last_end,如果当前区间的intervals[i].start>=last_end,则说明区间i可以保留,更新last_end=intervals[i].end。如果intervals[i].start<last_end,则当前区间会和上一个区间重叠,需要删除一个区间,为了使留下来的区间更多,肯定要删除end大的区间,令last_end=min(last_end,intervals[i].end),通过保留end小的区间来间接模拟删除end大的区间。
当得到保留下来的不重叠区间个数ans后,用n-ans就是需要删除的区间数。完整代码如下:

bool comp(const Interval &i1, const Interval &i2){
	return i1.start < i2.start || (i1.start == i2.start && i1.end < i2.end);
}
class Solution {
public:
    int eraseOverlapIntervals(vector<Interval>& intervals) {
    	if(intervals.empty()) return 0;
    	sort(intervals.begin(), intervals.end(), comp);
    	int ans = 1, n = intervals.size(), last_end = intervals[0].end;
    	for(int i = 1; i < n; ++i){
    		if(intervals[i].start >= last_end){
    			++ans;
    			last_end = intervals[i].end;
    		} else {
    			last_end = min(last_end, intervals[i].end);
    		}
    	}
    	return n - ans;
    }
};

本代码提交AC,用时9MS。

LeetCode Is Subsequence

LeetCode Is Subsequence
Given a string s and a string t, check if s is subsequence of t.
You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).
Example 1:
s = "abc", t = "ahbgdc"
Return true.
Example 2:
s = "axc", t = "ahbgdc"
Return false.
Follow up:
If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?


给定两个字符串s和t,判断s是否是t的子序列。子序列的概念和子串不一样,如果s是t的子串,则s必须是t中连续的一段;而如果是子序列的话,则s只需要是t中若干个字符,但这些字符顺序必须和t中的一样。
比如t="abcdefghijk",则"cdef"既可以是t的子串,也可以是t的子序列;而"bfjk"只能是t的子序列。
本题很简单,维护两个指针i,j,分别指向s和t,从t中不断找字符s[i],没找到只递增j,找到的话同时递增i和j。如果最后i到达s的末尾了,说明s是t的子序列,否则不是。
代码如下:

class Solution {
public:
	bool isSubsequence(string s, string t) {
		int m = s.size(), n = t.size();
		if (m > n)return false;
		int i = 0, j = 0;
		while (i < m&&j < n) {
			while (j < n&&s[i] != t[j])++j;
			if (j >= n)return false;
			++i;
			++j;
		}
		return i == m;
	}
};

本代码提交AC,用时73MS。

LeetCode Jump Game II

LeetCode Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note:
You can assume that you can always reach the last index.


上一题是问能否跳到数组右边,本题问最少需要多少跳能跳到数组右边,第一反应是DP。
设dp[i]表示从位置i跳到数组右边最少需要的跳数,则dp[n-1]=0,dp[0]就是最终结果。此时我们需要从数组右边往左边遍历,假设dp[i+1,...,n-1]都求出来了,现在要求dp[i]。站在位置i,我们最远能跳到i+A[i],所以我们就看看从i跳到哪个j\in[i,i+A[i]]能获得最少的跳数,从i跳到j需要增加一跳,所以递推式就是

dp[i]=min\{dp[j]+1\},\quad j\in[i+1,i+A[i]]


这种思路的代码如下:

class Solution {
public:
	int jump(vector<int>& nums) {
		int n = nums.size();
		if (n <= 1)return 0;
		int maxJump = n - 1;
		vector<int> dp(n, 0);
		for (int i = n - 2; i >= 0; --i) {
			int curMinJump = maxJump;
			for (int j = i + 1; j <= nums[i] + i&&j < n; ++j) {
				curMinJump = min(curMinJump, dp[j] + 1);
			}
			dp[i] = curMinJump;
		}
		return dp[0];
	}
};

可惜,本代码提交TLE,在最后一个大数据集上超时了。但是我还是觉得DP方法是一个基本法,而且如果要求出最小跳的路径,也很方便,如下代码,打印的时候,从pre[n-1]不断找前驱位置就好。

class Solution {
public:
	int jump(vector<int>& nums) {
		int n = nums.size();
		if (n <= 1)return 0;
		int maxJump = n - 1;
		vector<int> dp(n, 0), pre(n, 0);
		for (int i = n - 2; i >= 0; --i) {
			int curMinJump = maxJump, k = 0;
			for (int j = i + 1; j <= nums[i] + i&&j < n; ++j) {
				if (dp[j] + 1 < curMinJump) {
					curMinJump = dp[j] + 1;
					k = j;
				}
			}
			dp[i] = curMinJump;
			pre[k] = i; // 从i跳到k能获得最小跳数
		}
		return dp[0];
	}
};

讨论区看到一个O(n)的解法,很厉害。思路和上一题LeetCode Jump Game很类似,依旧维护一个当前能跳到的最远位置curFarthest,同时维护一个当前跳能跳到的范围[curBegin, curEnd],一旦i超过了curEnd,说明应该开启下一跳了,同时更新curFarthest。
这种算法的思路很巧妙,他不管你当前跳到底跳到哪里,只管你能够跳到的范围,一旦走出这个范围,就必须开启下一跳了。代码如下:

class Solution {
public:
	int jump(vector<int>& nums) {
		int jumps = 0, curEnd = 0, curFarthest = 0;
		for (int i = 0; i < nums.size() - 1; ++i) {
			curFarthest = max(curFarthest, i + nums[i]);
			if (i == curEnd) {
				curEnd = curFarthest;
				++jumps;
				if (curEnd >= nums.size() - 1)break;
			}
		}
		return jumps;
	}
};

本代码提交AC,用时22MS。第10行是增加的提前结束的代码。
参考:

LeetCode Jump Game

LeetCode Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.


给定一个数组,每个数字A[i]表示站在i位置最多能跳的步数,初始时站在数组左边,问能否跳到数组右边。
使用贪心策略,维护一个当前能跳到的最远位置maxpos。从左往右遍历数组,如果位置i>maxpos,说明根据之前的数字,没办法跳到位置i,直接break;否则更新maxpos为max(maxpos,A[i]+i)。最后检查maxpos>=n-1。完整代码如下:

class Solution {
public:
	bool canJump(vector<int>& nums) {
		int maxpos = 0;
		for (int i = 0; i < nums.size(); ++i) {
			if (i > maxpos)break;
			maxpos = max(maxpos, i + nums[i]);
		}
		return maxpos >= nums.size() - 1;
	}
};

本代码提交AC,用时12MS。

LeetCode Best Time to Buy and Sell Stock II

LeetCode Best Time to Buy and Sell Stock II
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).


还是股票买卖题。这一题不限制交易次数,但还是要求必须先卖出再买入,同一天可以先卖出再买入。
贪心策略,只要当前的股价比前一天高,则在前一天买入,当天卖出,能赚一点是一点,然后把每天赚的累加起来。
可能稍微会担心是否能得到最优解,比如价格是1,2,900,901,如果只交易一次,最好在第一天买入,最后一天卖出,收益901-1=900,但是贪心策略也一样:(2-1)+(900-2)+(901-900)=(901-1)=900。所以贪心能得到最优解。完整代码如下:

class Solution {
public:
	int maxProfit(vector<int>& prices) {
		int ans = 0;
		for (int i = 1; i < prices.size(); ++i) {
			if (prices[i] > prices[i - 1])ans += (prices[i] - prices[i - 1]);
		}
		return ans;
	}
};

本代码提交AC,用时9MS。

LeetCode Minimum Number of Arrows to Burst Balloons

LeetCode Minimum Number of Arrows to Burst Balloons
There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.
An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.
Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]
Output:
2
Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

平面上(可以看成是直线上)摆了很多个气球,气球有长度,占据了[s,t]的位置,气球之间可能会有重叠,现问最少用多少支箭能把所有气球射穿。
我们肯定希望把箭射在重叠气球最多的区域,但是不和其他气球重叠的气球终究要被射穿。我们可以采用贪心的策略,气球的区域用pair存储了,我们对所有气球的pair排序,得到先按start排序,再按end排序的一系列气球。
然后我们贪心的求重叠气球最多的区域,对于第一个气球,我们可以射[s1,t1],如果第二个气球的区域[s2,t2]和[s1,t1]有重叠,即s2<=t1,则这一箭可以射在重叠的区域,即[max(s1,s2),min(t1,t2)],我们再看第三个气球是否和[max(s1,s2),min(t1,t2)]有重叠,有的话又可以一箭三雕,此时又要更新重叠区域,如此循环下去。
具体怎样实现好呢,我们用end来记录当前重叠区域的结束位置。因为已经按pair排序了,如果后面气球的s小于等于前面重叠区域的end,则后面气球肯定会和重叠区域重叠,此时我们还需要更新新的重叠区域的end为之前的end和后面气球的t的最小值。这样相当于重叠区域在一步步收窄。当某个气球的s不再小于等于end时,前一个贪心阶段结束,需要新开一个重叠区域。
完整代码如下:

class Solution {
public:
	int findMinArrowShots(vector<pair<int, int>>& points) {
		if (points.size() == 0)return 0;
		sort(points.begin(), points.end());
		int i = 0, j = 1, end, ans = 0;
		while (i < points.size()) {
			end = points[i].second;
			while (j < points.size() && points[j].first <= end) {
				end = min(end, points[j].second);
				++j;
			}
			++ans;
			i = j++;
		}
		return ans;
	}
};

本代码提交AC,用时445MS。
参考:http://www.cnblogs.com/grandyang/p/6050562.html

LeetCode Assign Cookies

LeetCode Assign Cookies
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.
Example 1:

Input: [1,2,3], [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

Input: [1,2], [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

妈妈要给若干个孩子分饼干,没人一个饼干,不同饼干有不同的大小,同时不同孩子对饼干有一个最小的要求。问怎样分饼干才能满足最多的孩子的要求,求最多满足的孩子的数目。
明显是贪心的思路,把饼干从大到小排序,孩子的要求也从大到小排序,然后我们先尽量用大的饼干满足要求高的孩子,比如你会用一个100大小的饼干满足一个要求为90的孩子,而不是拿这个饼干满足要求为10的孩子,因为要求越低的孩子,被满足的可能性越高。如果当前最大的饼干都不能满足当前的孩子,则当前的策略满足不了这个孩子。
完整代码如下:

class Solution {
public:
	int findContentChildren(vector<int>& g, vector<int>& s) {
		sort(g.begin(), g.end());
		sort(s.begin(), s.end());
		int i = g.size() - 1, j = s.size() - 1, ans = 0;
		while (i >= 0) {
			if (j >= 0 && s[j] >= g[i]) {
				++ans;
				--j;
			}
			--i;
		}
		return ans;
	}
};

本代码提交AC,用时582MS。为什么会这么慢呀,后来试了下从小到大给孩子分饼干,也就是用能满足当前孩子的最小饼干,其实原理是一样的,尽量不浪费大的饼干:

class Solution {
public:
	int findContentChildren(vector<int>& g, vector<int>& s) {
		sort(g.begin(), g.end());
		sort(s.begin(), s.end());
		int i = 0, j = 0, ans = 0;
		while (i < g.size()) {
			while (j < s.size() && g[i] > s[j]) {
				++j;
			}
			if (j >= s.size())break;
			++ans;
			++i;
			++j;
		}
		return ans;
	}
};

AC了,但是还是很慢,449MS。。。

LeetCode Container With Most Water

LeetCode Container With Most Water
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.


题意是x轴上立着一堆线段,从这些线段中找两根和x轴构成一个木桶,问哪个木桶能装最多的水。
暴力枚举的话,是O(n^2)的。我们可以用贪心的思路来解决:要使木桶装更多的水,短板越长越好,且两根线之间的距离越长也越好。
设置首尾指针i,j,计算由i,j夹到的木桶的体积(这里简单点,面积即可),如果height[i]<height[j],则i++,因为短板越长越好,所以这相当于抛弃了height[i],保留height[j],底板减1。
完整代码如下:

class Solution {
public:
	int maxArea(vector<int>& height) {
		int mA = 0, i = 0, j = height.size() - 1;
		while (i != j)
		{
			int cur = min(height[i], height[j])*(j - i);
			if (cur > mA)
				mA = cur;
			if (height[i] < height[j])
				i++;
			else
				j--;
		}
		return mA;
	}
};

本代码提交AC,用时24MS。
二刷。
证明贪心方法的正确性一般用反证法,推出矛盾即可,证明过程见讨论区:https://discuss.leetcode.com/topic/503/anyone-who-has-a-o-n-algorithm

hihoCoder 1051-补提交卡

hihoCoder 1051-补提交卡
#1051 : 补提交卡
时间限制:2000ms
单点时限:1000ms
内存限制:256MB
描述
小Ho给自己定了一个宏伟的目标:连续100天每天坚持在hihoCoder上提交一个程序。100天过去了,小Ho查看自己的提交记录发现有N天因为贪玩忘记提交了。于是小Ho软磨硬泡、强忍着小Hi鄙视的眼神从小Hi那里要来M张"补提交卡"。每张"补提交卡"都可以补回一天的提交,将原本没有提交程序的一天变成有提交程序的一天。小Ho想知道通过利用这M张补提交卡,可以使自己的"最长连续提交天数"最多变成多少天。
输入
第一行是一个整数T(1 <= T <= 10),代表测试数据的组数。
每个测试数据第一行是2个整数N和M(0 <= N, M <= 100)。第二行包含N个整数a1, a2, ... aN(1 <= a1 < a2 < ... < aN <= 100),表示第a1, a2, ... aN天小Ho没有提交程序。
输出
对于每组数据,输出通过使用补提交卡小Ho的最长连续提交天数最多变成多少。
样例输入
3
5 1
34 77 82 83 84
5 2
10 30 55 56 90
5 10
10 30 55 56 90
样例输出
76
59
100


这一题想到那个点上就不难了,题目要求将补提交卡插入空缺的某天中,使连续提交天数最长。要使连续提交天数最长,补提交卡插入的位置也一定要是连续的,而且很方便的是,题目中给出的空缺天数都是递增的,所以不需要重新排序了。
既然需要满足插入的位置也要连续,那么总的方案数就没有那么多了。比如n=5,m=2,有如下几种方案:

左边的红色数字表示不同方案标号,这个标号也正好是该方案中数组a中的第一个插空位置的下标。很容易得到总的方案数有n-m+1个,所以我们只需将i从0到n-m+1循环枚举每一种方案,求最长的连续提交天数。
对于某一种方案,如上所述,其插空的开始下标正好为i,因为要插m个空,所以结束下标为m+i-1。那么这两者之间总的连续提交天数怎么算呢?比如上图中的方案2,如果把第55和56天填上,那么实际的连续提交天数应该是从31~89.也就是要从i-1对应的那天的后一天(31)算起,到m+i-1-1对应的那天的前一天(89)结束,总共就是89-31+1,也就是a[m+i-1+1]-a[i-1]-1;如果遇到最后一个空,因为m+i-1+1可能超过数组a的范围,所以我们添加一个a[n]=101,俗称哨兵;如果i==0的话,没有i-1,所以分开讨论。
最终的代码如下:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
     int t;
     cin>>t;
     int n,m;
     while(t--)
     {
          cin>>n>>m;
          vector<int> a(n+1);
          for(int i=0;i<n;i++)
               cin>>a[i];
          a[n]=101;//哨兵
          if(m>=n)
               cout<<100<<endl;
          else
          {
               int max_days=0;//最长连续提交天数
               int case_num=n-m+1;//总的枚举情况数
               for(int i=0;i<case_num;i++)
               {
                    int last_index=m+i-1;//该方案下最后一个下标
                    if(i==0)
                    {
                         if(a[last_index+1]-1>max_days)
                              max_days=a[last_index+1]-1;
                    }
                    else
                    {
                         if(a[last_index+1]-a[i-1]-1>max_days)
                              max_days=a[last_index+1]-a[i-1]-1;
                    }
               }
               cout<<max_days<<endl;
          }
     }
     return 0;
}

本代码提交AC,用时0MS,内存0MB。