読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Google Code Jam 2008 Round 1A : A. Minimum Scalar Product

GCJ

さてGCJ2001のRound1に行きます。
http://code.google.com/codejam/contest/32016/dashboard#s=p0

2つのベクトルが与えられるので、内積をとって最小になるようベクトルの要素を並べ替える。
片方を小さい順、片方を大きい順にして掛けて足すだけ。

int N;
s64 A[1001],B[1001];

void solve(int _loop) {
	int i,j,k,l;
	s64 res;
	
	N=GETi();
	FOR(i,N) A[i]=GETi();
	FOR(i,N) B[i]=GETi();
	sort(A,A+N);
	sort(B,B+N);
	
	res=0;
	FOR(i,N) res += A[i]*B[N-1-i];
	
	_PE("Case #%d: %lld\n",_loop,res);
}

まとめ

Round1の中でも特に簡単な問題だね。

広告を非表示にする