| 题目名称 | 2195. [USACO Feb15]负载平衡(白金组) |
|---|---|
| 输入输出 | Load_Balancing.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 15 |
| 题目来源 |
 Satoshi
于2016-04-04加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：46， 提交：109， 通过率：42.2% | ||||
 栋霸霸 |
100 | 0.330 s | 15.57 MiB | C++ |
 zhengtn03 |
100 | 0.377 s | 2.60 MiB | C++ |
 Flere825 |
100 | 0.452 s | 4.51 MiB | C++ |
 胡嘉兴 |
100 | 0.461 s | 18.44 MiB | C++ |
|
胡嘉兴 |
100 | 0.470 s | 18.44 MiB | C++ |
|
胡嘉兴 |
100 | 0.476 s | 20.34 MiB | C++ |
|
胡嘉兴 |
100 | 0.486 s | 20.34 MiB | C++ |
|
胡嘉兴 |
100 | 0.607 s | 20.34 MiB | C++ |
|
胡嘉兴 |
100 | 0.612 s | 20.34 MiB | C++ |
|
胡嘉兴 |
100 | 0.612 s | 20.34 MiB | C++ |
| 关于 负载平衡(白金组) 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
最正确的是暴力出奇迹！！
| ||||
|
回复 @Satoshi :
这个真的不是单峰的！样例一跑出来的就不是！ | ||||
|
写的K-D树为什么和暴力一样,似乎K-D树本身就很慢？？？......
 zys
2016-04-03 09:39
5楼
| ||||
|
小天使是我的，你萌不要和我抢
  asddddd
2016-03-31 19:54
4楼
| ||||
|
回复 @安呐。 :
调试了一晚上+一上午......  Satoshi
2016-03-31 12:34
3楼
| ||||
 安呐一条小咸鱼。
2016-03-31 11:38
2楼
| ||||
|
枚举一个轴，三分另一个轴，真TMD难写
图是我自己加的 这不是一道计算几何题，这不是一道计算几何题，这不是一道计算几何题，注意细节，注意细节，注意细节，重要的事情说三遍 需要写数据结构维护四个区域的点，最好是二叉排序树或者其他平衡树，树状数组维护逆序对也是可以的 官方是枚举+二分+线段树，我是枚举+三分 | ||||
FoolMike
2195. [USACO Feb15]负载平衡(白金组)
★★★★ 输入文件：Load_Balancing.in
输出文件：Load_Balancing.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
$Farmer John$的$N$头奶牛分别站在一个二维的农场里，坐标两两不同，分别为$X_i$和$Y_i(1<=N<=100000,$而且$X_i$和$Y_i$是正奇数，大小不超过$1000000)$,$FJ$想修建一堵东西向的无限长的篱笆(方程为$y=b$)和一堵南北向的无限长的篱笆（方程为$x=a$）从而把他的农场分成四部分(保证$a$和$b$为正偶数，为了不让篱笆经过任何一头奶牛的位置),这两条篱笆交于点$(a,b)$,他们把农场分成了四部分。
$FJ$想要选择$a$和$b$使得这四部分生成区域的奶牛”平衡”,每一个区域不能包含太多奶牛,
即令$M$为四个区域中最多的奶牛数，$FJ$想要让$M$尽量小。请帮助他算出$M$的最小值
【输入格式】
第一行一个正整数$n$，为奶牛的个数
接下来$n$行，为每个奶牛的坐标
【输出格式】
只有一行，为最小的$M$值
【样例输入】
7
7 3
5 5
7 13
3 1
11 7
5 3
9 1
【样例输出】
2
【提示】
对于40%的数据,$N<=1000$(银难度)
对于100%的数据,$N<=100000$（白金难度）
【来源】
USACO 2016 February contest Platinum