USACO 2016负载均衡优化算法

Question

这个问题出现在USACO 2016年2月铜牌比赛（问题3）

Farmer John's NN cows are each standing at distinct locations (x1,y1)…(xn,yn) on his two-dimensional farm (1 ≤ N ≤ 100), and the xi's and yi's are positive odd integers of size at most B). FJ wants to partition his field by building a long (effectively infinite-length) north-south fence with equation x=a (a will be an even integer, thus ensuring that he does not build the fence through the position of any cow). He also wants to build a long (effectively infinite-length) east-west fence with equation y=b, where b is an even integer. These two fences cross at the point (a,b), and together they partition his field into four regions.

FJ wants to choose a and b so that the cows appearing in the four resulting regions are reasonably "balanced", with no region containing too many cows. Letting M be the maximum number of cows appearing in one of the four regions, FJ wants to make M as small as possible. Please help him determine this smallest possible value for M.

For the first five test cases, B is guaranteed to be at most 100. In all test cases, B is guaranteed to be at most 1,000,000.

我使用了一个暴力算法来获得前5个测试用例的正确性，这5个测试用例运行了大约0（n^2）的时间，但是很明显，如果B是一个很大的数字，这是行不通的。

然后，我试图通过在数据点的中位数附近放置两个围栏来缩短解决方案的时间，但这似乎不起作用。

代码如下：

fin = open('balancing.in', 'r');
fout = open('balancing.out', 'w');
xcows = [];
ycows = []
mincows = 10000;
N, B = map(int, fin.readline().split());
for i in range(N):
    x1, y1 = map(int, fin.readline().split());
    xcows.append(x1);
    ycows.append(y1);

xlow,ylow,xhigh,yhigh = 0,0,0,0;

xmedian = -1;
xxcows = sorted(xcows)
yycows = sorted(ycows)
if len(xxcows)%2==0:
    med = len(xxcows)//2;
    xmedian = int(xxcows[med] + xxcows[med-1])//2;
else:
    med = len(xxcows)//2;
    xmedian = xxcows[med];
xlow = (xmedian//2)-1;
xhigh = (xmedian//2)+1;

ymedian = -1;
if len(yycows)%2==0:
    med = len(yycows)//2;
    ymedian = int(yycows[med] + yycows[med-1])//2;
else:
    med = len(yycows)//2;
    ymedian = yycows[med];

ylow = (ymedian//2)-1;
yhigh = (ymedian//2)+1;

for xx in range(xlow-1, xhigh+2):
    for yy in range(ylow-1, yhigh+2):
        #place boundary at x = xx and y = yy and count cows in each quadrant
        q1, q2, q3, q4 = 0, 0, 0, 0;
        for q in range(len(xcows)):
            if xcows[q] < xx*2 and ycows[q] > yy*2:
                q1+=1;
            elif xcows[q] > xx*2 and ycows[q] > yy*2:
                q2+=1;
            elif xcows[q] < xx*2 and ycows[q] < yy*2:
                q3+=1;
            elif xcows[q] > xx*2 and ycows[q] < yy*2:
                q4+=1;
        mini = max(q1, q2, q3, q4);
        if mincows > mini:
            mincows = mini;

fout.write(str(mincows));
fin.close();
fout.close();

这个代码只有2/10的测试用例是正确的。我不明白为什么这个算法不起作用。如果有更好的算法，请随意分享，因为我被难住了。

Answer 1

该方法不依赖于B的大小，仅依赖于牛的数量，N为每席尝试将N S线设为席1。对于每一个彝族，试着在彝-1上画一条东西线。因为最多有100头奶牛，最多也就有1万箱可供尝试。在

import itertools as it

# your code for reading cow data goes here

for xx, yy in it.product(xcows, ycows):
    counts = [0,0,0,0]
    for x,y in cows:
        ew = 0 if x < xx else 2
        ns = 0 if y < yy else 1
        counts[ew + ns] += 1

    mini = max(counts)

# rest of you code goes here

Answer 2

寻找更多的牛是更好的策略。下面的程序从最初的猜测开始，尝试将栅栏移到下一个位置东西、南北和对角，看看是否能提高分数。与当前最佳分数匹配的任何围栏位置都将保持一个队列。当队列为空时，答案是当前的最佳分数和位置。在

取消对print语句的注释以查看它是如何工作的。在

from collections import deque

def calc_score(ew_fence, ns_fence):
    cnts = [0,0,0,0]
    for cow in cows:
        i = (0 if cow[1] < ew_fence else 2) + (0 if cow[0] < ns_fence else 1)
        cnts[i] += 1
    return max(cnts)

def solve2(cows):
    xs,ys = zip(*cows)

    xs = sorted(x-1 for x in set(xs))
    ix = len(xs)//2

    ys = sorted(y-1 for y in set(ys))
    iy = len(ys)//2

    #print("Initial score = {} at ix,iy = ({},{})".format(calc_score(xs[ix],ys[iy]), ix, iy))

    seen = set([(ix, iy)])

    queue = deque([(ix, iy)])

    best_score, best_ix, best_iy = calc_score(xs[ix],ys[iy]), ix, iy

    while queue:
        ix, iy = queue.pop()
        #print("checking near: ix,iy = ({}, {})".format(ix, iy))

        for dx,dy in ((-1, 1), (0, 1), (1, 1),
                      (-1, 0),         (1, 0),
                      (-1,-1), (0,-1), (1,-1)):

            nx, ny = ix + dx, iy + dy

            if (nx,ny) in seen: 
                #print("\t({},{}) - seen".format(nx, ny))
                continue

            seen.add((nx, ny))
            score = calc_score(xs[nx], ys[ny])

            if score < best_score:
                best_score, best_ix, best_iy = score, nx, ny
                #print("\t({},{}) - new best score = {}".format(best_ix, best_iy, best_score))
                queue.clear()

            if score == best_score:
                queue.append((nx, ny))
                #print("\t({},{}) = enqueue".format(nx, ny))

    #print("\nbest score = {} at ix,iy = ({},{}) = grid coords ({},{})".format(
    #        best_score, best_ix, best_iy, xs[best_ix], ys[best_iy]))

    return best_score, (xs[best_ix], ys[best_iy])