Hướng dẫn giải của Phân số lớn nhất (đề HSG 12 Khánh Hòa 2020-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
Chọn hai số làm tử và mẫu (tử $\ne$ mẫu về vị trí) sao cho tử $<$ mẫu và ti số lớn nhất. Với mỗi mẫu $b$, tử tốt nhất là số lớn nhất nhỏ hơn $b$. Nếu nhiều cặp cho cùng ti số lớn nhất thì chọn cặp có tử nhỏ hơn.
Sub 1: Vét cạn — ~O(N^2)~, dùng khi ~N \le 1000~
Thử mọi cặp chỉ số $(i, j)$ với $Ai < Aj$, so sánh các phân số bằng phép nhân chéo.
Nếu chỉ nộp sub này: đúng 15/20 test (5 test lớn quá giờ).
Sub 2: Sắp xếp — ~O(N \log N)~
Sắp các giá trị khác nhau. Với mỗi phần tử $b$ (trừ phần tử nhỏ nhất), tử tốt nhất chính là phần tử đứng ngay trước $b$ trong dãy đã sắp. Chỉ cần thử các cặp liền kề này. Bẫy: nhân chéo cho ti số nên giá trị đến $10^{18}$, vẫn nằm trong long long.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc dữ liệu từ file MAXF.inp, ghi ra MAXF.out. Nếu $N \le 1000$ thì gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
int N;
vector<long long> A; // A[0..N-1], so nguyen khong am
// So sanh phan so x1/y1 voi x2/y2 (y > 0): tra ve true neu x1/y1 > x2/y2
bool greaterFrac(long long x1, long long y1, long long x2, long long y2) {
return x1 * y2 > x2 * y1;
}
// Chon cap tot hon: ti so lon hon; neu bang nhau thi lay cap co tu so nho hon
void consider(long long a, long long b, bool &has, long long &ba, long long &bb) {
if (!has) {
has = true; ba = a; bb = b;
return;
}
if (greaterFrac(a, b, ba, bb) || (a * bb == ba * b && a < ba)) {
ba = a; bb = b;
}
}
// Sub 1: vet can O(N^2), dung khi N <= 1000.
// Thu moi cap (tu so i, mau so j) voi A_i < A_j.
void sub1() {
bool has = false;
long long ba = 0, bb = 1;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (i != j && A[i] < A[j]) consider(A[i], A[j], has, ba, bb);
if (!has) cout << -1 << "\n";
else cout << ba << " " << bb << "\n";
}
// Sub 2: O(N log N). Voi mau so b co gia tri cho truoc, tu so lon nhat < b la
// gia tri lien truoc b trong day da sap xep (bo trung). Chi can thu cap do.
void sub2() {
vector<long long> v = A;
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
bool has = false;
long long ba = 0, bb = 1;
for (size_t k = 1; k < v.size(); k++)
consider(v[k - 1], v[k], has, ba, bb);
if (!has) cout << -1 << "\n";
else cout << ba << " " << bb << "\n";
}
int main() {
freopen("MAXF.inp", "r", stdin);
freopen("MAXF.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
A.resize(N);
for (auto &x : A) cin >> x;
if (N <= 1000) sub1();
else sub2();
return 0;
}
Bình luận