torus711 のアレ

主に競技プログラミングの問題について書きます

SRM 578, Division 2, Level 1 : DeerInZooDivTwo

概要

N 匹の鹿がいて、最初はそれぞれが二本の角を持っている。
その後、何匹かの鹿は一本または二本の鹿を無くしてしまい、その総数は K である。
二本の角を持っている鹿の最小値と最大値を求めよ。

解法

最小値は、できるだけ多くの鹿が一本ずつ無くした場合です。
ただし、0 未満になってはいけないので max( 0, N - K ) です。
最大値は、できるだけ多くの鹿が二本ずつ無くした場合なので、N - K / 2 - K % 2 です。

コード

typedef vector<int> VI;

class DeerInZooDivTwo
{
public:
	vector <int> getminmax( int N, int K )
	{
		VI res( 2 );
		res[0] = max( 0, N - K );
		res[1] = N - K / 2 - K % 2;
		return res;
	}
};