【二分】【2020.8.24NOIP模拟赛】选数排列

$Link$Link

$luogu\ T145305$luogu T145305

$Description$Description

$Sample$Sample $Input$Input

7 2 3
170 205 225 190 260 225 160

$Sample$Sample $Output$Output

30

$Hint$Hint

$Solution$Solution

排个序，直接二分
预处理出$i\ \ \ \ \ to\ \ \ \ \ i +c - 1$i     to     i+c−1的差，然后直接判断一下就好了

$Code$Code

#include<algorithm>
#include<iostream>
#include<cstdio>

using namespace std;

int p[500005], cha[500005];
int n, r, c, ans;
const int inf = 1e9;

bool check(int mid)
{
	int num = 0;
	for (int i = 1; i <= n - c + 1; ++i)
	{
		if (cha[i] <= mid) {
			num++;
			i += c - 1;
		}
	}
	return num >= r;
}

int main()
{
	scanf("%d%d%d", &n, &r, &c);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &p[i]);
	sort(p + 1, p + n + 1);
	for (int i = c; i <= n; ++i)
	 cha[i - c + 1] = p[i] - p[i - c + 1];
	int L = 0, R = inf;
	while (L <= R)
	{
		int mid = (L + R) / 2;
		if (check(mid)) R = mid - 1, ans = mid;
		else L = mid + 1;
	}
	printf("%d", ans); 
}