[数据结构与算法]BZOJ [WF2013] Low Power（二分

#3969. [WF2013]Low Power
思路：
好像是道很水的二分
问题还是怎么 $check$ 判掉什么时候开始不合法
这个题用一个 $l$ 指针，通过判断选出的相邻点对相距是否过大，这样其实是不可行的
因为选出一个点对就意味着后边还可以容纳 $2?(m?1)$ 个点，我们每选出一对相邻的点，就意味着容量的增大，只要从头开始的任意一段，点对的容量始终大于等于没有选择的点数量，就合法
因此应该通过容量来判断
$cnt$ 计数表示选出的点对个数，总容量就是 $2?cnt?m$
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define mem(x, d) memset(x, d, sizeof(x))
#define eps 1e-6
using namespace std;
const int maxn = 2e6 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
ll a[maxn];

bool check(ll x){
	ll cnt = 0;
	for(int i = 1; i <= 2 * n * m; ++i){
		if(a[i+1] - a[i] <= x) ++cnt, ++i;
		if(cnt >= n) return 1;
		if(2 * cnt * m < i) return 0;// 总容量小于总点数
	}
	return 0;
}
void work()
{
	cin >> n >> m;
	for(int i = 1; i <= 2 * n * m; ++i) cin >> a[i];
	sort(a + 1, a + 1 + 2 * n * m);
	ll l = 0, r = inf;
	while(l < r){
		ll mid = l + r >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l;
}

int main()
{
	ios::sync_with_stdio(0);
//	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}

中位数切分
思路：
感觉和这道题蛮像
ACcode