Hướng dẫn giải của [200 đề thầy Đức] Bài 160: Độ lệch trong dãy
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cần chọn đúng n - m số trong dãy. Độ lệch lớn nhất là hiệu giữa tổng n - m số lớn nhất và tổng n - m số nhỏ nhất.
Sub 1: Vét cạn chọn dần — ~O(n^2)~
Lấy lần lượt n - m số lớn nhất (mỗi lần quét cả dãy tìm số lớn chưa dùng), rồi làm tương tự với số nhỏ nhất. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<long long> a(n);
for (auto &x : a) cin >> x;
int k = n - m; // cần chọn đúng k số
// Vét cạn: lấy lần lượt k số lớn nhất, rồi k số nhỏ nhất
vector<bool> used(n, false);
long long lon = 0, nho = 0;
for (int t = 0; t < k; t++) {
int best = -1;
for (int i = 0; i < n; i++)
if (!used[i] && (best == -1 || a[i] > a[best])) best = i;
used[best] = true;
lon += a[best];
}
fill(used.begin(), used.end(), false);
for (int t = 0; t < k; t++) {
int best = -1;
for (int i = 0; i < n; i++)
if (!used[i] && (best == -1 || a[i] < a[best])) best = i;
used[best] = true;
nho += a[best];
}
cout << lon - nho << "\n";
}
return 0;
}
Sub 2: Sắp xếp — ~O(n log n)~
Sắp xếp dãy tăng dần. Tổng nhỏ nhất là tổng k số đầu, tổng lớn nhất là tổng k số cuối (k = n - m). Đạt 21/21 test. Dùng long long cho tổng.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<long long> a(n);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
int k = n - m; // số phần tử cần chọn
long long nho = 0, lon = 0;
for (int i = 0; i < k; i++) nho += a[i]; // k số nhỏ nhất
for (int i = n - k; i < n; i++) lon += a[i]; // k số lớn nhất
cout << lon - nho << "\n";
}
return 0;
}
Bình luận