回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>这个问题出现在USACO 2016年2月铜牌比赛(问题3)</p>
<blockquote>
<p>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.</p>
<p>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.</p>
<p>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.</p>
</blockquote>
<p>我使用了一个暴力算法来获得前5个测试用例的正确性,这5个测试用例运行了大约0(n^2)的时间,但是很明显,如果B是一个很大的数字,这是行不通的。</p>
<p>然后,我试图通过在数据点的中位数附近放置两个围栏来缩短解决方案的时间,但这似乎不起作用。</p>
<p>代码如下:</p>
<pre><code>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.<a href="https://www.cnpython.com/list/append" class="inner-link">append</a>(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();
</code></pre>
<p>这个代码只有2/10的测试用例是正确的。我不明白为什么这个算法不起作用。如果有更好的算法,请随意分享,因为我被难住了。</p>