Skip to content

Instantly share code, notes, and snippets.

@binux

binux/3666.cpp Secret

Created March 28, 2018 18:24
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save binux/1fc354bfd95836e92f19e3250527b2c9 to your computer and use it in GitHub Desktop.
Save binux/1fc354bfd95836e92f19e3250527b2c9 to your computer and use it in GitHub Desktop.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void insertSort(vector<int> &l, int n) {
vector<int>::iterator low = lower_bound(l.begin(), l.end(), n);
l.insert(low, n);
}
int f(vector<int>l, int minimum=1) {
if (l.size() == 0) return 0;
if (l.size() == 1) {
return abs(l[0] - max(l[0], minimum));
}
int medians_min = 1000000000 + 1;
int index;
vector<int> sorted_l;
for (int i = l.size() - 1; i >= 0; i--) {
insertSort(sorted_l, l[i]);
int m = sorted_l[(sorted_l.size()-1)/2];
if (m < medians_min) {
index = i;
medians_min = m;
}
}
//cout << index << " " << medians_min << endl;
int m = max(minimum, medians_min);
vector<int> left(l.begin(), l.begin() + index);
int sum = 0;
for (int i = index; i < l.size(); i++) {
sum += abs(m - l[i]);
}
return f(left, m) + sum;
}
int main()
{
int n;
cin >> n;
vector<int> l;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
l.push_back(x+1);
}
//int a = f(l);
reverse(l.begin(), l.end());
int b = f(l);
//cout << min(a, b) << endl;
cout << b << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment