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

kmjp's blog

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

Rockethon 2014 Trial Contest: A2. Skis

Codeforces

Rockethonは時間も時間なので不参加。
とはいえ練習だけしてみます。
http://codeforces.com/contest/395/problem/A2

問題

N個の整数と整数Qが与えられる。
N個の整数から、和がQとなる対をいくつ作れるか。
ただし、一度Qを作るのに使った整数は2度は使えない。

解法

N個の整数を端から処理していく。
整数xに対して、Q-xが1個以上あれば、対を作っていけばよい。

int rr[1000001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>i>>j;
	x=0;
	FOR(f,i) {
		cin>>y;
		if(y>=j) continue;
		if(rr[j-y]) x++,rr[j-y]--;
		else rr[y]++;
	}
	_P("%d\n",x);
}

まとめ

これはかなりお試し的な簡単な問題だね。

広告を非表示にする