P6172 [USACO16FEB]Load Balancing P

Load Balancing P

将平面直角坐标系中的点用两条平行于 \(x/y\) 轴的直线分成 \(4\) 部分，求区域内最多奶牛数量的最小值。

二分答案，难点在判定上。

按照普通贪心思路，枚举 \(x\) 后枚举 \(y\)，那显然是 \(O(n^2\log n)\) 的，跑到天荒地老。

所以需要使用数据结构优化这个过程可以考虑从小到大枚举 \(y\)（\(x\) 也是一样的），然后在树状数组上二分。

但是这样是 \(O(n\log^3 n)\) 看上去很不优美，发现可以双指针一遍扫过去，于是就变成 \(O(n\log ^2 n)\) 了。

考虑实现将 \(x\) 离散化一下可以达到更加优美的复杂度哦。

#include
#include
#include
using namespace std;

const int N = 100010;
int n, m, b[N], up[N], down[N];
struct node{int x, y;} a[N];

int read(){
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

bool cmp(node a, node b){return a.y < b.y;}

void Modify(int c[], int x, int v){for(; x <= m; x += x & -x) c[x] += v;}
int Query(int c[], int x){int sum = 0; for(; x; x -= x & -x) sum += c[x]; return sum;}

bool chck(int mid){
	int Up = n, Down = 0, S = 1, T = n;
	for(int i = 1; i <= n; i ++) up[i] = down[i] = 0;
	for(int i = 1; i <= n; i ++) Modify(up, a[i].x, 1);
	for(int i = 1, j; i <= n; i = j){
		j = i;
		while(a[i].y == a[j].y){
			Modify(up, a[j].x, - 1);
			Modify(down, a[j].x, + 1);
			j ++, Up --, Down ++;
		}
		while(S <= n && Query(up, S) <= mid) S ++; S --;
		while(T >= 1 && Query(down, T) > mid) T --;
		int t = min(S, T);
		if(Up - Query(up, t) <= mid && Down - Query(down, t) <= mid)
			return true;
	}
	return false;
}

int main(){
	n = read();
	for(int i = 1; i <= n; i ++){
		a[i].x = read(), a[i].y = read();
		b[i] = a[i].x;
	}
	sort(b + 1, b + n + 1);
	m = unique(b + 1, b + n + 1) - (b + 1);
	for(int i = 1; i <= n; i ++)
		a[i].x = lower_bound(b + 1, b + m + 1, a[i].x) - b;
	sort(a + 1, a + n + 1, cmp);
	int l = 0, r = n;
	while(l < r){
		int mid = (l + r) >> 1;
		if(chck(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", l);
	return 0;
}