arius1408's blog

By arius1408, history, 2 years ago, In English

While I'm doing problems on CSES like always, I met with a rather interesting problem : CSES-Stick Lengths. After solving it, I discover there was actually atleast 3 ways to do this problem (all in O(NlogN)): the one I used to AC, other one using Ternary Search, and finally, using a prominent solution that I saw others used. The idea for the third was short : You sort the whole array, take the median (N/2) as the target value and calculate the result using it. Here it how it goes on USACO :

#include <bits/stdc++.h>

using namespace std;

//variables used for the current problem
int n,median;
vector<int> p;
long long ans,cnt;

void solve() {
	cin >> n;
	p.resize(n);
	for (int &x : p){
		cin >> x;
	}
	sort(p.begin(),p.end());
	median=p[n/2];
	for (const int &x : p){
		ans+=abs(median-x); //Calculate the cost to modify the stick length
	}
	cout << ans << "\n";
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
	return 0;
}

After a while of observation, I myself must admit the solution's correctness. But I just couldn't proof it. Can you guys help me with it ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what method did you use I understood 1. ternary search method 2. Median method 3. ?