STEAD - Steady Cow Assignment
题意翻译
农夫约翰的 $N$ 头牛各自居住在 $B$ 个牛棚之一中。当然,这些牛棚容量有限制。一些牛喜欢它们目前居住的牛棚,另一些并不怎么喜欢。
FJ希望重新安排奶牛,使奶牛尽可能快乐,即使这意味着所有的奶牛都讨厌他们指定的谷仓。
每头牛给约翰这些牛棚在它们心目中的位置(不会有两个牛棚在某头牛心目中处于同等位置),一头牛的开心值为它所住牛棚在它心目中的位置。
你的任务就是牛(开心值最大值与最小值之差)的最小值。
### 输入输出格式
- 第 $1$ 行:两个整数 $N$、$B$ 表示牛数与牛棚数。
- 第 $2\sim N+1$ 行:每行 $B$ 个整数表示各个牛棚在它心目中的地位。
- $N+2$ 行:$B$ 个整数,表示牛棚容量。
输出一个整数表示「开心值最大值与最小值之差」的最小值。
题目描述
Farmer John's N (1 <= N <= 1000) cows each reside in one of B (1 <= B <= 20) barns which, of course, have limited capacity. Some cows really like their current barn, and some are not so happy.
FJ would like to rearrange the cows such that the cows are as equally happy as possible, even if that means all the cows hate their assigned barn.
Each cow gives FJ the order in which she prefers the barns. A cow's happiness with a particular assignment is her ranking of her barn. Your job is to find an assignment of cows to barns such that no barn's capacity is exceeded and the size of the range (i.e., one more than the positive difference between the the highest-ranked barn chosen and that lowest-ranked barn chosen) of barn rankings the cows give their assigned barns is as small as possible.
输入输出格式
输入格式
Line 1: Two space-separated integers, N and B
Lines 2..N+1: Each line contains B space-separated integers which are exactly 1..B sorted into some order. The first integer on line i+1 is the number of the cow i's top-choice barn, the second integer on that line is the number of the i'th cow's second-choice barn, and so on.
Line N+2: B space-separated integers, respectively the capacity of the first barn, then the capacity of the second, and so on. The sum of these numbers is guaranteed to be at least N.
输出格式
One integer, the size of the minimum range of barn rankings the cows give their assigned barns, including the endpoints
输入输出样例
输入样例 #1
6 4
1 2 3 4
2 3 1 4
4 2 3 1
3 1 2 4
1 3 4 2
1 4 2 3
2 1 3 2
输出样例 #1
2