Hướng dẫn giải của SETMAP08: Đừng là con bò cuối cùng
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
Tính tổng sữa của từng chú bò (chú nào không xuất hiện thì tổng là 0). Gọi M là tổng nhỏ nhất. Cần tìm tổng nhỏ nhất lớn hơn M; nếu đúng một chú bò đạt tổng đó thì in tên, nếu có nhiều chú hoặc không có tổng nào lớn hơn M thì in "Tie".
Chỉ viết 1 sub vì bài chỉ cần cộng dồn và so sánh một lần, không có cách vét cạn nào khác đáng kể. Đạt 20/20 test.
Sub 1: Cộng dồn và so sánh — ~O(n)~
Cộng tổng sữa của 7 chú bò theo tên, lấy M là giá trị nhỏ nhất, tìm giá trị nhỏ nhất lớn hơn M, rồi đếm số chú bò có giá trị đó. Dùng long long vì tổng có thể lớn.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<string> cows = {"Bessie", "Elsie", "Daisy", "Gertie", "Annabelle", "Maggie", "Henrietta"};
vector<long long> records(n);
vector<string> names(n);
for (int i = 0; i < n; i++) cin >> names[i] >> records[i];
// Vét cạn: với mỗi chú bò, quét toàn bộ danh sách để cộng tổng sữa
vector<long long> total(cows.size(), 0);
for (size_t c = 0; c < cows.size(); c++)
for (int i = 0; i < n; i++)
if (names[i] == cows[c]) total[c] += records[i];
// M là lượng sữa ít nhất (có thể bằng 0 nếu có chú bò không xuất hiện)
long long M = *min_element(total.begin(), total.end());
// Tìm giá trị nhỏ nhất > M
bool found = false;
long long best = 0;
for (long long t : total)
if (t > M && (!found || t < best)) { best = t; found = true; }
if (!found) { cout << "Tie\n"; return 0; }
// Đếm số chú bò có tổng đúng bằng best
int cnt = 0, idx = -1;
for (size_t c = 0; c < cows.size(); c++)
if (total[c] == best) { cnt++; idx = (int)c; }
if (cnt == 1) cout << cows[idx] << "\n";
else cout << "Tie\n";
return 0;
}
Bình luận