Created
February 14, 2019 14:33
-
-
Save GauthamBanasandra/97d3994d7f93deb22a2caa2b383ca6bc to your computer and use it in GitHub Desktop.
Sherlock and cost
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <vector> | |
#include <algorithm> | |
#include <iostream> | |
class CostEstimator | |
{ | |
public: | |
explicit CostEstimator(const std::vector<int> &numbers) :numbers_(numbers) {} | |
int Estimate() const; | |
private: | |
int ComputeCost(bool take_max) const; | |
const std::vector<int> &numbers_; | |
}; | |
int CostEstimator::Estimate() const | |
{ | |
return std::max(ComputeCost(true), ComputeCost(false)); | |
} | |
int CostEstimator::ComputeCost(bool take_max) const | |
{ | |
if (numbers_.size() == 1) | |
{ | |
return numbers_.front(); | |
} | |
auto cost = 0; | |
for (std::size_t i = 1, len = numbers_.size(); i < len; ++i) | |
{ | |
if (take_max) | |
{ | |
cost += std::abs(numbers_[i - 1] - 1); | |
} | |
else | |
{ | |
cost += std::abs(1 - numbers_[i]); | |
} | |
take_max = !take_max; | |
} | |
return cost; | |
} | |
int main(int argc, char* argv[]) | |
{ | |
std::size_t t, num_len; | |
std::vector<int> numbers{ 10, 1, 10, 1, 10 }; | |
std::cin >> t; | |
while (t--) | |
{ | |
std::cin >> num_len; | |
numbers.resize(num_len); | |
for (std::size_t i = 0; i < num_len; ++i) | |
{ | |
std::cin >> numbers[i]; | |
} | |
CostEstimator estimator(numbers); | |
std::cout << estimator.Estimate() << std::endl; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment