CSES - Stick Lengths

Authors: Danh Ta Chi Thanh, Sofia Yang

Table of Contents

SolutionImplementation

In this problem, we are given an array with nn elements. We want to find the minimum cost to make all of the elements equal.

Solution

Unofficial Editorial

Another solution and some proofs

Implementation

Here is the code implementation for the easiest approach.

C++

#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() {

Java

import java.io.*;
import java.util.*;
public class StickLengths {
Code Snippet: Kattio (Click to expand)
public static void main(String[] args) {
Kattio io = new Kattio();
int N = io.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N; i++) { arr[i] = io.nextInt(); }

Python

n = int(input())
sticks = sorted(list(map(int, input().split())))
median = sticks[n // 2]
ans = 0
for x in sticks:
ans += abs(median - x)
print(ans)

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!