9.9科大讯飞笔试算法T3---二分+贪心+结论 100%

那个Ir的规定

等价于任意长为2和长为3的数字平均数大于等于m

因为任意长为x的偶数的话都能分割成长为2的，奇数的话分成若千个长为2的和一个长为3的

所以，直接二分答案，贪心子序列，从大到小，在遍历判断2，3

复杂度为Olgn*n*2*3

可以过

#include <iostream> 
#include <cstring>
#include <algorithm>
using namespace std;

int n, m; 
int a[100010];
bool check(int x)
{
	for(int i = 2; i <= x - 1; i ++)
	{
		double tmp = 1e9;
		// 2 的情况 
		tmp = (double) 1.0 * (a[i] + a[i - 1]) / 2;
		if(tmp < m) return false;
		tmp = (double) 1.0 * (a[i] + a[i + 1]) / 2;
		if(tmp < m) return false;
		
		// 3 的情况 
		if(i >= 3) tmp = (double) 1.0 * (a[i - 2] + a[i - 1] + a[i]) / 3; 
		if(tmp < m) return false;
		
		tmp = (double) 1.0 * (a[i - 1] + a[i] + a[i + 1]) / 3; 
		if(tmp < m) return false;
		
		if(i + 2 <= x) tmp = (double) 1.0 * (a[i] + a[i + 1] + a[i + 2]) / 3; 
		if(tmp < m) return false;
	}
	return true;
}
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	sort(a + 1, a + n + 1, greater<int>());
	
	int l = 0, r = n;
	while(l < r)
	{
		int mid = l + r + 1 >> 1;
		if(check(mid)) l = mid;
		else r = mid - 1; 
	}
	cout << r << endl;
}