Jinglei's blog
0%

「题解」洛谷P3138 Load Balancing S

Posted on Edited on

题目链接

洛谷：https://www.luogu.com.cn/problem/P3138

10pts：简单的骗分

在笔记本上画了幅图，手动找了下正确答案，然后就有了第一个思路

把水平方向和竖直方向的栅栏分开找。方法很简单，让每条栅栏可以使栅栏两边奶牛数的差尽量小。

思想有些像贪心？

具体实现的话，就是找奶牛横坐标与纵坐标的中位数，作为栅栏的横坐标和纵坐标。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <iostream>
#include <algorithm>

const int Maxn=1005;
int n, x, y, xa[Maxn], ya[Maxn], xy[Maxn][2], p1, p2, p3, p4, xx, yy, maxx;

int main(){
//	freopen("data.in", "r", stdin);
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%d %d", &x, &y);
		xa[i]=x;
		ya[i]=y;
		xy[i][1]=x; xy[i][2]=y;
	}
	std::sort(xa, xa+n);
	std::sort(ya, ya+n);
	if(n&1){
		xx=(xa[n/2]+xa[n/2-1])/2;
		yy=(ya[n/2]+ya[n/2-1])/2;
	}
	else{
		xx=xa[n/2-1];
		yy=ya[n/2-1];
	}

	for(int i=0; i<n; i++){
		if(xy[i][1]>xx && xy[i][2]>yy) p1++;
		if(xy[i][1]<xx && xy[i][2]>yy) p2++;
		if(xy[i][1]>xx && xy[i][2]<yy) p3++;
		if(xy[i][1]<xx && xy[i][2]<yy) p4++;
	}
	maxx=p1;
	maxx=maxx>p2?maxx:p2;
	maxx=maxx>p3?maxx:p3;
	maxx=maxx>p4?maxx:p4;
	printf("%d", maxx);

	return 0;
}

当然是错的……

100pts：离散化+前缀和

其实这题大家看到第一反应一定是前缀和吧，包括我也是一样的。可惜在我看到数据范围 10610^6 的时候就立马放弃了。

在写了上面的代码wa了之后，我注意到了题目背景：

本题与 白金组同名题目 在题意上一致，唯一的差别是数据范围。

于是我看了那个数据范围不同的题目，那道题中，NN 的范围从 10310^3 增加到了 10510^5 ，难度也从黄变成了紫。

所以 NN 的范围这个才是影响题目难度的关键，和 xix_i 、 yiy_i 关系不大。于是我想起了离散化。

把横坐标和纵坐标分别离散化处理，这样就可以大大降低复杂度，只需要开到 10310^3 的二维数组就好了。

然后把处理好的二维数组计算前缀和，然后挨个枚举横纵坐标。

边界要稍微留心一下，也没有其他的坑了。（这是我第一次写二维离散化，一次就过了，可想而知这道题没什么坑……

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <iostream>
#include <algorithm>

const int Maxn=1005, Maxx=1e6+5;
int n, x, y, xa[Maxn], ya[Maxn], xy[Maxn][2], p1, p2, p3, p4, xx, yy, minx=0x7fffffff;
int sm[Maxn][Maxn], mapp[Maxn][Maxn], xm[Maxx], ym[Maxx], xp, yp, cntx, cnty;

int main(){
//	freopen("data.in", "r", stdin);
	scanf("%d", &n);
	for(int i=1; i<=n; i++){
		scanf("%d %d", &x, &y);
		if(xm[x]==0){
			xa[++cntx]=x;
			xm[x]++;
		}
		if(ym[y]==0){
			ya[++cnty]=y;
			ym[y]++;
		}
		xy[i][0]=x; xy[i][1]=y;
	}
	std::sort(xa+1, xa+1+cntx);
	std::sort(ya+1, ya+1+cnty);

	for(int i=1; i<=n; i++){
		xp = std::lower_bound(xa+1, xa+1+cntx, xy[i][0])-xa;
		yp = std::lower_bound(ya+1, ya+1+cnty, xy[i][1])-ya;
		mapp[xp][yp]++;
	}
	
	for(int i=1; i<=cntx; i++){
		for(int j=1; j<=cnty; j++){
			sm[i][j] = sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+mapp[i][j];
		}
	}
	for(int i=1; i<=cntx; i++){
		for(int j=1; j<=cnty; j++){
			p1 = sm[i][j];
			p2 = sm[cntx][j]-p1;
			p3 = sm[i][cnty]-p1;
			p4 = n-p1-p2-p3;
			p1 = p1>p2?p1:p2;
			p1 = p1>p3?p1:p3;
			p1 = p1>p4?p1:p4;
			minx = minx<p1?minx:p1;
		}
	}
	printf("%d", minx);

/*	if(n&1){
		xx=(xa[n/2]+xa[n/2-1])/2;
		yy=(ya[n/2]+ya[n/2-1])/2;
	}
	else{
		xx=xa[n/2-1];
		yy=ya[n/2-1];
	}

	for(int i=0; i<n; i++){
		if(xy[i][1]>xx && xy[i][2]>yy) p1++;
		if(xy[i][1]<xx && xy[i][2]>yy) p2++;
		if(xy[i][1]>xx && xy[i][2]<yy) p3++;
		if(xy[i][1]<xx && xy[i][2]<yy) p4++;
	}
	maxx=p1;
	maxx=maxx>p2?maxx:p2;
	maxx=maxx>p3?maxx:p3;
	maxx=maxx>p4?maxx:p4;
	printf("%d", maxx);
*/
	return 0;
}

（其实我一开始看到“最大值最小”的时候，第一反应是二分答案，不过之后就想不下去了，而这正好是那道紫题的正解）