作者RockLee (Now of all times)
看板Prob_Solve
标题[问题] Google Code Jam 2010, Round 2 - C
时间Fri Feb 24 16:00:02 2012
题目叙述网址:
http://code.google.com/codejam/contest/635102/dashboard#s=p2
我想到的 algorithm 只能在限定时间内跑完 small data set,
遇到 large data set 就无力了 Orz...
看了前几名的 algorithm, 关键似乎在於,
一开始相邻的 bacteria 的长方形,
存在的时间会是相邻长方形中 (Max(X2) + Max(Y2)) 扣掉
相邻长方形中任一个的 (X1 + Y1) 得到的值中最大的那一个再加一.
相邻长方形个数为 1 或 2 时, 这样的关系还蛮明显的.
但个数更多时, 这样的关系似乎没那麽直觉.
有高手可以进一步说明或证明为何有这样的关系吗?
[Jonick's solution in Java]
import java.io.*;
public class c implements Runnable
{
BufferedReader in;
BufferedWriter out;
final static int INF = 10000000;
public class Rect
{
int x1, y1, x2, y2;
Rect(int x1, int y1, int x2, int y2)
{
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
}
public boolean isOverlapped(int s1, int f1, int ss1, int ff1)
{
int ms = Math.max(s1, ss1);
int mf = Math.min(f1,ff1);
return mf - ms >= -1;
}
public boolean canJoin(Rect r)
{
if( !isOverlapped(x1,x2,r.x1,r.x2) ) return false;
if( !isOverlapped(y1,y2,r.y1,r.y2) ) return false;
if( x1 == r.x2 + 1 && y1 == r.y2 + 1 ) return false;
if( r.x1 == x2 + 1 && r.y1 == y2 + 1 ) return false;
return true;
}
}
int color[];
public void join(int n, int c1, int c2 )
{
for( int i = 0; i < n; i++ )
{
if( color[i] == c2 )
{
color[i] = c1;
}
}
}
public void solve() throws Exception
{
int n = Integer.parseInt(readword());
color = new int[n];
Rect a[] = new Rect[n];
for( int i = 0; i < n; i++ )
{
color[i] = i;
a[i] = new Rect(Integer.parseInt(readword()),
Integer.parseInt(readword()),
Integer.parseInt(readword()),
Integer.parseInt(readword()));
}
for( int i = 0; i < n; i++ )
for( int j = i+1; j < n; j++ )
{
if( a[i].canJoin(a[j]) )
{
join(n,color[i],color[j]);
}
}
int answer = 0;
for( int i = 0; i < n; i++ )
{
boolean hasColor = false;
for( int j = 0; j < n; j++ )
{
if( color[j] == i )
{
hasColor = true;
break;
}
}
if( !hasColor )
{
continue;
}
int maxX = -INF;
int maxY = -INF;
for( int j = 0; j < n; j++ )
{
if( color[j] == i )
{
maxX = Math.max(maxX, a[j].x2);
maxY = Math.max(maxY, a[j].y2);
}
}
for( int j = 0; j < n; j++ )
{
if( color[j] == i )
{
int tmp = maxX - a[j].x1 + maxY - a[j].y1;
if( tmp > answer ) answer = tmp;
}
}
}
out.write((answer+1) + "\n");
}
public String readword() throws IOException
{
int c = in.read();
while( c >= 0 && c <= ' ' ) c = in.read();
if( c < 0 ) return "";
StringBuilder bld = new StringBuilder();
while( c > ' ' ) {
bld.append((char)c);
c = in.read();
}
return bld.toString();
}
public void run()
{
try
{
in = new BufferedReader(new FileReader(this.getClass().getName() +
".in"));
out = new BufferedWriter(new FileWriter(this.getClass().getName() +
".out"));
int tn = Integer.parseInt(readword());
for(int i = 0; i < tn; i++ )
{
out.write("Case #" + (i+1) + ": ");
solve();
}
out.flush();
}
catch( Exception e )
{
e.printStackTrace();
System.exit(1);
}
}
public static void main(String[] args)
{
new Thread(new c()).start();
}
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.137.134.119