torus711 のアレ

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

2013 TCO Algorithm - Round 1A, Level 1 : HouseBuilding

概要

グリッド状の土地に家を建てたい。
しかし、この土地の高さがバラバラで家を建てることができない。
そこで、土地の高さの最大値と最小値の差が 1 以内となるように整地したい。
一回の操作で一つのグリッドの高さを 1 変えることができるとき、最小何回の操作で整地できるか求めよ。

解法

整地された土地の高さは高々二つ ( k, k + 1 ) になります。
この目標の高さを総当りして、全てのセルについて目標値のいずれかとの差の絶対値の小さい方の総和をとります。

コード

typedef vector<string> VS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class HouseBuilding
{
public:
	int getMinimum( vector <string> area )
	{
		int res = INT_MAX;
		REP( i, 0, 9 )
		{
			res = min( res, test( area, i, i + 1 ) );
		}
		return res;
	}

	int test( const VS &area, const int &t1, const int &t2 )
	{
		const int H = area.size(), W = area[0].size();
		int res = 0;

		REP( i, 0, H )
		{
			REP( j, 0, W )
			{
				res += min( abs( ( area[i][j] - '0' ) - t1 ), abs( ( area[i][j] - '0' ) - t2 ) );
			}
		}

		return res;
	}
};