Ryhmässä $A$ on $n$ koodaria ja ryhmässä $B$ on myös $n$ koodaria. Tehtäväsi on muodostaa $n$ paria, joissa molemmissa on koodari ryhmästä $A$ ja $B$. Kunkin koodarin tulee olla tasan yhdessä parissa.

Jokaisella koodarilla on tietty taitotaso, ja parien taitotasojen tulisi olla lähellä toisiaan. Kun parin taitotasot ovat $x$ ja $y$, tästä tulee sakkoa $|x-y|$. Sinun tulee etsiä ratkaisu, jossa sakkojen yhteissumma on mahdollisimman pieni.

Voit olettaa, että $n$ on enintään $10^5$ ja jokainen taitotaso on kokonaisluku välillä $1 \dots 10^9$. Tavoitteena on, että algoritmin aikavaativuus on $O(n \log n)$.

Python

Toteuta tiedostoon coders.py funktio find, joka ilmoittaa pienimmän sakkojen yhteissumman.

def find(a,b):
    # TODO

if __name__ == "__main__":
    print(find([1,2,3],[2,5,2])) # 3
    print(find([2],[7])) # 5
    print(find([1,1,1,1],[3,4,3,4])) # 10
    print(find([5,2,9,1,2,4],[8,8,2,3,9,4])) # 11

Java

Toteuta tiedostoon Coders.java metodi find, joka ilmoittaa pienimmän sakkojen yhteissumman.

public class Coders {
    public long find(int[] a, int[] b) {
        // TODO
    }

    public static void main(String[] args) {
        Coders c = new Coders();
        System.out.println(c.find(new int[] {1,2,3}, new int[] {2,5,2})); // 3
        System.out.println(c.find(new int[] {2}, new int[] {7})); // 5
        System.out.println(c.find(new int[] {1,1,1,1}, new int[] {3,4,3,4})); // 10
        System.out.println(c.find(new int[] {5,2,9,1,2,4}, new int[] {8,8,2,3,9,4})); // 11
    }
}