思路：用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序，选取最大的M-1个作为间隙，其余地方用木板盖住。 做法： 1.若，板（M） 的数目大于或等于 牛棚中有牛的数目（C），则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则，先对 牛牛们的门牌号排序，然后 用一个数组 blank[ ] 记录两门牌号之间的距离，然后 用数组 an

题目 [ 传送门 ]         题目描述         作为当代建筑的爱好者，Farmer John 建造了一个圆形新谷仓，谷仓内部 个房间排成环形，按顺时针顺序编号为，每个房间都有通往与其相邻的左右房间的门，还有一扇门通往外面。         现在 FJ 有 n 头奶牛，他的目标是让每个房间恰好有一头奶牛。然而不幸的是，现在奶牛们随意呆在某个房间里，第 i 个房间里有 ​ 头奶牛

Barn Repair Description 在一个夜黑风高、下着暴风雨的夜晚，farmer John的牛棚的屋顶、门都被吹飞了。所幸，许多牛都在度假，所以牛棚并没有住满。 牛棚一个挨着一个相邻排列成一行，牛就在里面过夜。一些牛棚里面有牛，而一些没有。所有的牛棚都有相同的宽度。 自从门被吹走后，farmer John必须尽快地在牛棚前建立新的木板。他的新木料供应商将会供应给他任意他想要长度的

n<=10000个点(xi,yi)，找到一个不同于给出的所有点的点，使得该点到所有点的曼哈顿距离最小并找出这样的点的个数。 第一眼看上去这不是中位数嘛，奇数一个点偶数一片，然后找一下这篇区域有几个不符合的点即可。不过要找出“不同于给出的点”的点，那万一中位数那个点被占了，就找它四周四个点即可。 错误！明知道会有中位数那一个点被占了，那怎么就不考虑四周都被占了的情况？ 不过可以肯定的是，离中位数越

Description 经过多年的积蓄，农夫JOHN决定造一个新的牛舍。他知道所有N(2 <= N <= 10,000)头牛的吃草位置，所以他想把牛舍造在最方便的地方。 每一头牛吃草的位置是一个整数点(X_i, Y_i) (-10,000 <= X_i <= 10,000; -10,000 <= Y_i <= 10,000)。 没有两头牛的吃草位置是相邻的。 JOHN决定把牛舍造在一个没有牛吃

1696: [Usaco2007 Feb]Building A New Barn新牛舍 Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 394  Solved: 181[Submit][Status][Discuss] Description 经过多年的积蓄，农夫JOHN决定造一个新的牛舍。他知道所有N(2 <= N <= 10,000)头牛的吃

思路： 这本暴力思路是不是很清晰，但是纯暴力这数据范围必t，我们观察发现其实耗时就是标记涂过的地方，所以我们现在将重心放在我们该如何优化上，不卖关子了，其实这是一个非常经典的二维前缀和优化~（具体细节观看代码，稳稳AC） ACcode: #include<bits/stdc++.h>using namespace std;#define int long longconst in

题目描述 在一个夜黑风高,下着暴风雨的夜晚,farmer John的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚没有住满。 牛棚一个紧挨着另一个被排成一行，牛就住在里面过夜。 有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。 自门遗失以后,farmer John必须尽快在牛棚之前竖立起新的木板。 他的新木材供应商将会供应他任何他想要的长度,但是吝啬的供应商只能提供有限数目的木板。