Hướng dẫn giải của [200 đề thầy Đức] Bài 146: Sô cô la
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
Vova ăn mỗi lần một miếng ở đầu trái hoặc đầu phải của thanh sô cô la, miếng cuối cùng còn lại thuộc về em gái. Cần tìm độ ngon của miếng đó khi Vova luôn ăn miếng ngon hơn trong hai đầu.
Cách làm
Dùng hai chỉ số l (đầu trái) và r (đầu phải), ban đầu l = 0 và r = N - 1. Trong khi l < r, so sánh a[l] với a[r]: nếu a[l] > a[r] thì Vova ăn miếng bên trái (tăng l), ngược lại ăn miếng bên phải (giảm r). Khi l = r thì chỉ còn đúng một miếng, in a[l].
Bẫy: phải đọc đủ N số của bộ dữ liệu trước khi xử lý, và T bộ dữ liệu được xử lý lần lượt.
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// Vova luôn ăn miếng ngon hơn trong hai miếng đầu,
// nên miếng cuối cùng còn lại chính là miếng em gái nhận được
int l = 0, r = n - 1;
while (l < r) {
if (a[l] > a[r]) {
l++; // ăn miếng đầu trái
} else {
r--; // ăn miếng đầu phải
}
}
cout << a[l] << "\n";
}
return 0;
}
Bình luận