Only Premium Users can view the Question
Understand the Goal:
You are given n
data centers and n
servers, placed on a 1D number line.
You need to pair each data center with exactly one server such that the total lag (absolute difference) is minimized.
Key Insight:
This is a classic case of minimum sum of absolute differences between two arrays with 1:1 mapping.
To minimize the sum:
➤ Sort both arrays
➤ Pair i-th
element from center[]
with i-th
element from destination[]
.
Why this works?
Based on the Rearrangement Inequality, pairing sorted elements minimizes the sum of absolute differences.
Steps:
Read input arrays center[]
and destination[]
.
Sort both arrays.
For each index i
from 0 to n-1
, compute abs(center[i] - destination[i])
.
Sum up all those values and print the result.
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> d_cen(n), des(n);
for (int i = 0; i < n; i++) cin >> d_cen[i];
int m;
cin >> m;
for (int i = 0; i < m; i++) cin >> des[i];
sort(d_cen.begin(), d_cen.end());
sort(des.begin(), des.end());
long long totalLag = 0;
for (int i = 0; i < n; i++) {
totalLag += abs(d_cen[i] - des[i]);
}
cout << totalLag << endl;
}
Sorting both arrays: O(n log n)
Computing lag: O(n)
Total TC = O(n log n)
Using O(n)
space for two arrays.
Total SC = O(n)
The key insight is to efficiently count elements smaller than each array element in two ranges:
lower_bound()
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> arr(n);
for(int i = 0 ; i < n;i++){
cin >> arr[i];
}
multiset<int> s;
int k;
cin >> k;
vector<int> left(n,0),right(n,0);
for (int i = 0; i < n; ++i) {
left[i] = distance(s.begin(), s.lower_bound(arr[i]));
s.insert(arr[i]);
}
s.clear();
for (int i = n - 1; i >= 0; --i) {
right[i] = distance(s.begin(), s.lower_bound(arr[i]));
s.insert(arr[i]);
}
int cnt = 0;
for (int i = k; i < n-k; ++i) {
cout << arr[i] << endl;
cout << left[i] << " " << right[i] << endl;
if (left[i] >= k && right[i] >= k)
cnt++;
}
cout << cnt << endl;
}
O(n log n) - Two passes through array with multiset insert and lower_bound operations
O(n) - For multiset, left array, right array, and input storage