algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.cpp (1225B)


      1 #include <iostream>
      2 #include <vector>
      3 #include <unordered_set>
      4 #include <unordered_map>
      5 #include <algorithm>
      6 
      7 #define ll long long
      8 
      9 using namespace std;
     10 
     11 int main() {
     12 
     13     int testCases, current, size;
     14 
     15     cin >> testCases;
     16     for(int z = 0; z < testCases; ++z) {
     17 
     18         cin >> size;
     19         vector<ll> ls{};
     20 
     21         for(int i = 0; i < size; ++i) {
     22             cin >> current;
     23             ls.push_back(current);
     24         }
     25 
     26         sort(ls.begin(), ls.end());
     27 
     28         int leftMatch = 1;
     29         int rightMatch = 1;
     30         ll changeBy = 0;
     31 
     32         ll cost = 0;
     33 
     34         while(leftMatch + rightMatch <= (int)ls.size()) {
     35             if(leftMatch < rightMatch) {
     36                 // lock left
     37 
     38                 ll delta = ls[leftMatch] - ls[leftMatch-1];
     39                 changeBy -= delta;
     40                 cost += leftMatch * delta;
     41                 leftMatch += 1;
     42                 
     43             } else {
     44                 // lock right
     45                 ll delta = ls[ls.size() - rightMatch] - ls[ls.size() - rightMatch - 1];
     46                 changeBy -= delta;
     47                 cost += rightMatch * delta;
     48                 rightMatch += 1;
     49             }
     50         }
     51         cout << cost << " " << ls.back() - ls[0] << endl;
     52     }
     53 }