Hướng giải của Leo đồi 1D

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời giải

Sử dụng các thuật toán tìm kiếm địa phương (Hill Climbing, Simulated Annealing).

Mô phỏng thuật toán Hill Climbing: bắt đầu từ vị trí \(start\), tại mỗi bước xét hai láng giềng trái/phải, di chuyển đến láng giềng có giá trị lớn hơn. Lặp đến khi không thể di chuyển.

Độ phức tạp: \(O(N)\) trong trường hợp xấu nhất.

Hướng dẫn giải

Sử dụng thuật toán phù hợp để giải quyết bài toán.

Mã nguồn C++

// Giải thuật ls cho bài toán ls-hill-1d\n#include <bits/stdc++.h>
using namespace std;
int main() {
    // Doc du lieu dau vao
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    // Tim dinh bang leo doi
    int pos = 0;
    while (true) {
        if (pos > 0 && a[pos-1] > a[pos]) pos--;
        else if (pos < n-1 && a[pos+1] > a[pos]) pos++;
        else break;
    }
    cout << a[pos] << "\n";
    return 0;
}

```

Nhận xét

Không có ý kiến tại thời điểm này.