2021CCPC广州 C. Necklace（二分/贪心/好题/详细题解）

Bob has given Alice a necklace as her birthday gift. That necklace has ??N crystals, ??M of which catches her fancy. Formally, crystals with labels of 1..??1..N are strung sequentially in a circle. And those catching her fancy are labelled ??1,??2,...,????n1,n2,...,nM.

Alice would like the necklace to be divided into ??M pieces. She asked Bob to sever the necklace into ??M pieces. Each piece should consist of a sequence of crystals as in the original necklace (i.e., the crystal labels are contiguous, except that 11 following ??N is accepted) and should include one crystal catching Alice's fancy. Obviously, each crystal must belong to exactly one piece.

However, an excessively long piece of severed necklaces could not fit Alice's slim neck. So she wants to know, among all possible severings as requested, what the minimum length of the longest piece from a severed necklace is. She wants you to answer this question.

Input

The first line of the input data contains 2 integers ??N and ??M (1≤??≤??<10181≤M≤N<1018 and ??≤106M≤106).

The second line contains ??M integers, the ??i-th of which represents ????ni. The ????ni's are given in ascending order.

Output

You need to output your answer in one line.

Example

input

Copy

10 4
2 5 6 8

output

Copy

3

Note

As for the example: You can sever the necklace into [1,3],[4,5],[6,7],[8,10][1,3],[4,5],[6,7],[8,10].

Considering huge scale of data, here is a way provided to help input faster:

看了题解没看懂（出题人语文水平堪忧，后来自己像明白了还各种写错变量wa了十发，绷不住了

首先最大值最小的问题一眼二分，关键在于check函数怎么写。首先一个贪心思路是对于从左到右对于每个特殊的宝石在满足左边的需求时尽可能往右取。比如对于题目样例，如果二分到的值是2的话，一开始2作为左端点，尽可能往右取能取到[2,3]这个区间，此时第二个特殊的宝石是5，显然4这个宝石没法被第一个区间覆盖，那么第一个区间的需求就是1，那么枚举到5的时候，首先要满足需求，所以第二个区间只能是[4,5]...如果最终能首尾接上则可行。但这么贪心显然是错的，比如对于样例：

10 3
3 5 7

最优策略一定是5覆盖4和6，然后3与7尽量向两边扩展，但上述贪心无法很好地利用中间的5。但这个思想可以启发我们，最终的贪心策略不是能给则给，而是“满足则不给，不满足则尽可能少地给使之满足”。同样也是枚举特殊宝石，对于第一个宝石，我们先让它为长为x的段的右端点；然后从左往右遍历特殊的宝石，设上一个区间的右端点为lst，当前特殊宝石位置为i，先尽量往左覆盖再尽量往右覆盖，如果能把上一个区间的右端点到当前特殊宝石这段区间都覆盖的话就可以尽量往右覆盖了，如果lst + 1 < i - x，说明尽量往左覆盖的话已经不够用了，此时需要从第一个区间开始，所有区间往右移动（当然有可能存在区间使得移动不起作用），看看能否满足覆盖i - 1到i这段区间，只要能覆盖那么就只移动这段距离绝不多移动，如果移动到头还不能覆盖则check(x)应该返回false。遍历一遍以后看看最后一个区间的右端点能否和第一个区间的左端点接上，如果接不上则返回false，否则返回true。那么还有一个问题，如何判断是否还能移动呢？这时候可以维护两个变量offset以及each_min_offset，offset记录第一个段往右移动的距离，each_min_offset记录的是当前整体能往右移动的距离，维护each_min_offset的关键思想就是用每一段的左端点到这段的特殊宝石的距离来更新each_min_offset（取最小）。

比如对于样例：

10 3
2 5 9

假设二分的值为3，一开始第一段是[10, 1, 2], offset = 0, each_min_offset = 2（第一段的左端点最大为2，所以10到2可以移动两步），lst = 2；枚举到5时先往左取再往右，此时[3, 4, 5]已经用光了，且不需要整体移动，因此offset = 0, each_min_offset = 2, lst = 5；枚举到9时，尽量往左取也只能取出来[7, 8, 9]，无法覆盖6，因此需要整体移动，此时each_min_of set = 2,可以往右最多移动两步，但我们只让它往右移动一步，所以offset = 1, each_min_offset = 1（此时当前段的左端点到当前特殊宝石的距离肯定大于each_min_offset了），lst = 9。遍历完后，第一个区间左端点向右移动offset个距离，变为了1.此时最后一个区间的右端点是9，第一个区间的左端点是1，中间相差一个10，因此无法衔接，故check(3) = false。

具体细节见代码。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define int long long
#define ll long long
#define pb push_back
using namespace std;
int n, m, M[1000005];

//6 3
//3 4 5
bool check(ll mid) {
	ll offset = 0, lst = M[1];
	int each_min_offset = mid - 1;
	int len = mid;
	int res = 0;
	bool yuejie1 = 0, yuejie2 = 0;//判断第一个区间的左端点和最后一个区间的右端点是否跨越了n到1
	//第一个特殊的一开始作为第一段的最后一个
	for(int i = 2; i <= m; i++) {
		if(len >= M[i] - lst) {
			res = len - (M[i] - lst);//能够往右扩展的
			lst = M[i] + res;
			if(i == m) {
				if(lst > n) {
					lst %= n;
					lst = min(lst, M[1] - 1);
					yuejie1 = 1;
				}
			} else {
				lst = min(lst, M[i + 1] - 1);//注意不能把特殊宝石也包含进去
			}
			each_min_offset = min(each_min_offset, M[i] - lst - 1);//这里要给each_min_offset取min进行更新
		} else {
			if(M[i] - M[i - 1] + 1 > 2 * len) return false;//凑不出来
			int need = M[i] - lst - len;//需要整体移动的距离
			if(need > each_min_offset) return false;//无法满足
			each_min_offset -= need;//最多能往右移动的距离需要减小
			offset += need;
			lst = M[i];
		}
	}
	int lmst = lst, rmst;//这里的lmst是最后一个区间右端点的位置，rmst是第一个区间左端点的位置
	if(M[1] - len + 1 + offset >= 1) rmst = M[1] - len + 1 + offset;
	else {
		yuejie2 = 1;
		rmst = n + M[1] - len + 1 + offset;
	}
	//判断能否接上，写丑了QoQ
	if(yuejie1 && yuejie2) {
		return 1;
	} else if(yuejie1) {
		return lmst >= rmst - 1;
	} else if(yuejie2) {
		return lmst >= rmst - 1;
	} else {
		if(lmst == n && rmst == 1) return 1;
		else return 0;
	}

}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		cin >> M[i];
	}
	if(m == 1) {
		cout << n;
		return 0;
	}
	ll l = 1, r = n, mid;
	while(l < r) {
		mid = (l + r) >> 1;
			//cout << mid << endl;
		if(check(mid)) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	cout << l;
	return 0;
}
// 20 3
// 4 7 10

//20 3
//5 6 7 8 9 ?

// 20 5
// 1 2 3 5 8
算法基础—贪心题库—比赛重现赛算法基础—三分

相关

标签