Hướng dẫn giải của Nghe nhạc (đề Bình Định 2021)
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
Phát bài ở vị trí ~p~ trên băng, máy phải quay bỏ qua tổng thời lượng các bài trước ~p~, rồi phát bài đó. Tổng thời gian khi mỗi bài phát một lần là tổng các thời gian này. Để tổng nhỏ nhất, xếp bài ngắn trước, bài dài sau.
Sub 1: sắp xếp tăng dần theo thời lượng — ~O(N \log N)~
Chỉ viết một sub vì bài chỉ cần một công thức: sắp xếp tăng dần theo thời lượng rồi in thời gian của từng bài và tổng. Đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc N và thời lượng, gọi sub1 (bài chỉ có một sub).
#include <bits/stdc++.h>
using namespace std;
// Bai hat i co thoi luong d[i]. Khi phat bai o vi tri p tren bang, may phai
// quay bo qua cac bai truoc do (tong thoi luong cac bai o vi tri 1..p-1) roi phat bai do.
// Moi bai duoc phat dung 1 lan, nen tong thoi gian = tong cac tong tien to.
// Muon tong nho nhat, xep bai ngan truoc, bai dai sau (sap xep tang dan theo thoi luong).
// Bai nay chi can mot cach giai (sap xep), nen chi viet mot sub.
// Ly do: loi giai tham lam tang dan la dung va du nhanh cho moi kich thuoc du lieu.
void sub1(int n, const vector<long long> &d) {
vector<int> ord(n);
for (int i = 0; i < n; i++) ord[i] = i;
stable_sort(ord.begin(), ord.end(), [&](int x, int y) { return d[x] < d[y]; });
long long pref = 0; // tong thoi luong cac bai da xep truoc do
long long total = 0; // tong thoi gian quay bang khi moi bai phat mot lan
for (int p = 0; p < n; p++) {
int j = ord[p];
long long t = pref + d[j]; // quay bo qua cac bai truoc, roi phat bai j
cout << j + 1 << " " << t << "\n";
total += t;
pref += d[j];
}
cout << total << "\n";
}
int main() {
freopen("nhac.inp", "r", stdin);
freopen("nhac.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> d(n);
for (int i = 0; i < n; i++) cin >> d[i];
sub1(n, d);
return 0;
}
Bình luận