每日一题~p4447(贪心)

添加链接描述
题意：
一串数字，数值相邻的数字可以划分为一组。问 人数最少的组，的最大值是多少。

贪心的思路：
用a数组记录数字
用b数组记录每组的最大实力值**（因为每组的最大值 决定了当前元素是否能够 进入 这个组）**
用c数组记录每组的人数

对a排序之后枚举a[i]，
在b 数组种 二分查找 小于等于 a[i]-1的最后一组
如果找到的值等于 a[i]-1，那么a[i]接到该组。
否则就 ，重新开一组。

贪心：
二分查找最后一组，是因为 后开的组，人数少，把a[i]接入 最后一组，会使得 该组人数 增多。答案更优。
例:
2 3 3 4 5 7 8 9
4 就应该 接到 {3}，而不是{2，3}

#include <bits/stdc++.h>
using namespace std;

int main() {
	std::cin.tie(nullptr)->sync_with_stdio(false); 
	int n;
	cin>>n;
	vector<int>a(n);
	//记录 每组的最大值，和人数
	vector<int>b;
	vector<int>c;
	int cnt=0;//代表组数
	for (int i=0; i<n; i++)
		cin>>a[i];
	sort(a.begin(),a.end());
	for (int i=0,k; i<n; i++) {
		//找小于等于 a[i]-1的最后一个数
		int it=upper_bound(b.begin(),b.end(),a[i]-1)-b.begin()-1;
			if (b.empty()||it<0) 
		{	
			b.push_back(a[i]);
			c.push_back(1);
			cnt++;
		} 
		else {
			if (b[it]==a[i]-1) 
			{
			
				b[it]=a[i];
				c[it]++;
			}
			else {
			b.push_back(a[i]);
			c.push_back(1);
			cnt++;
			}
		}
	}
	int ans=1e9;
	for (int i=0; i<cnt; i++) {
		ans=min(ans,c[i]);
	}
	cout<<ans<<"\n";
	
	return 0;
}