文章

68

粉丝

691

获赞

26

访问

578.3k

头像
二分法适合做最大化最小值,最小化最大值等等
P1638
发布于2020年5月31日 19:53
阅读数 8.7k

 

二分法,尺取法,折半枚举,都算是比较常见的题吧

#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<string.h>
#include<set>
#include<unordered_map>
#include<cstdio>
using namespace std;

#define ll long long
#define inf 0x3f3f3f3f
#define MAX 100005
#define vec vector<int>
#define P pair<int,int>

int N, C;
ll x[MAX];
//以k作为最小距离是否可以
bool check(ll k) {
	ll pre = x[0], cnt = 1;
	for (int i = 1; i < N; i++) {
		if (x[i] - pre >= k) {
			cnt++; pre = x[i];//在这里放个牛
		}
	}
	if (cnt >= C)return true;
	else return false;
}

int main() {
	while (cin >> N >> C) {
		for (int i = 0; i < N; i++)cin >> x[i];
		sort(x, x + N);
		ll l = 0, r = x[N - 1];
		while (r - l > 1) {
			ll mid = (l + r) >> 1;
			if (check(mid))l = mid;
			else r = mid;
		}
		cout << l << endl;
	}
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发