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
    }
}