Skip to content

Instantly share code, notes, and snippets.

@GauthamBanasandra
Created February 14, 2019 14:33
Show Gist options
  • Save GauthamBanasandra/97d3994d7f93deb22a2caa2b383ca6bc to your computer and use it in GitHub Desktop.
Save GauthamBanasandra/97d3994d7f93deb22a2caa2b383ca6bc to your computer and use it in GitHub Desktop.
Sherlock and cost
#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