Cho bốn số n, x, a, b. Có n học sinh đứng thành một hàng. Hai học sinh đối thủ đứng ở vị trí a và b (vị trí đánh số từ 1 đến n từ trái sang phải). Ta muốn tối đa hóa khoảng cách giữa hai học sinh này. Có thể thực hiện thao tác sau tối đa x lần: chọn hai học sinh liền kề và hoán đổi vị trí của chúng. Hãy tìm khoảng cách tối đa có thể đạt được sau x lần hoán đổi.
Ví dụ
Nếu n = 5; x = 1; a = 3; b = 2, đầu ra là 2. Vì ta có thể hoán đổi học sinh ở vị trí 3 và 4, khi đó khoảng cách là |4 - 2| = 2.
Giải thuật
Khoảng cách ban đầu là |a - b|. Mỗi lần hoán đổi có thể tăng khoảng cách lên tối đa 1 (bằng cách đẩy một trong hai học sinh ra phía ngoài). Tuy nhiên, khoảng cách tối đa không thể vượt quá n - 1 (khi một học sinh ở đầu, một ở cuối). Do đó, kết quả là min(|a - b| + x, n - 1).
Mã C++
#include <bits/stdc++.h>
using namespace std;
int solve(int n, int x, int a, int b) {
return min(abs(a - b) + x, n - 1);
}
int main() {
int n = 5;
int x = 1;
int a = 3;
int b = 2;
cout << solve(n, x, a, b) << endl;
}
Đầu vào / Đầu ra
Input: 5, 1, 3, 2
Output: 2