TopCoder practice room (purely for fun)
Problem Statement
Manao is building a new house. He already purchased a rectangular area
where he will place the house. The basement of the house should be
built on a level ground, so Manao will have to level the entire area.
The area is leveled if the difference between the heights of its lowest
and highest square meter is at most 1. Manao wants to measure the
effort he needs to put into ground leveling. You are given a
vector <string> area. Each character in area denotes the height
at the corresponding square meter of Manao's area. Using 1 unit of
effort, Manao can change the height of any square meter on his area by
1 up or down. Return the minimum total effort he needs to put to obtain
a leveled area.
Definition
Class:
HouseBuilding
Method:
getMinimum
Parameters:
vector <string>
Returns:
int
Method signature:
int getMinimum(vector <string> area)
(be sure your method is public)
Limits
Time limit (s):
2.000
Memory limit (MB):
64
Constraints
-
area will contain between 1 and 50 elements, inclusive.
-
Each element of area will be between 1 and 50 characters long, inclusive.
-
All elements of area will be of the same length.
-
Each element of area will contain digits ('0'-'9') only.
Examples
0)
{"10",
"31"}
Returns: 2
The given area is not leveled, because the minimum height is 0 and the
maximum height is 3. Manao needs to reduce the height of lower left
square by 2.
1)
{"54454",
"61551"}
Returns: 7
In the optimal solution each square will have height either 4 or 5. To
reach such a configuration, Manao should reduce the height of one
square from 6 to 5, and increase the heights of two other squares from
1 to 4.
2)
{"989"}
Returns: 0
The area is already leveled.
3)
{"90"}
Returns: 8
4)
{"5781252",
"2471255",
"0000291",
"1212489"}
Returns: 53
This problem statement is the exclusive and proprietary property of
TopCoder, Inc. Any unauthorized use or reproduction of this information
without the prior written consent of TopCoder, Inc. is strictly
prohibited. (c)2003, TopCoder, Inc. All rights reserved.
//////////////////////////////////////////////////////////////////////////////////
#include <vector>
#include <string>
using namespace std;
class HouseBuilding
{
public:
int getMinimum(vector<string> area)
{
int current = 199999999;
for (char ch = '0'; ch < '9'; ch ++)
{
int sum = 0;
for (size_t i = 0; i < area.size(); i ++)
{
for (size_t j = 0; j < area[i].size(); j ++)
{
char tmp = area[i][j] - ch;
if (tmp > 1)
{
sum += tmp-1;
}
else
{
if (tmp < 0)
{
sum += -tmp;
}
}
}
}
if (sum < current)
{
current = sum;
}
}
return current;
}
};