Gợi ý

Subtask 1

• Dùng backtrack để xét hết tất cả trường hợp.

Subtask 2

• Với ~a_i = n~, duyệt từ người thứ ~1~ đến ~n~:
  • Gọi ~cnt~ là số người được mời tham dự buổi tiệc khi duyệt đến người thứ ~i~, nghĩa là ~cnt~ là số người không giàu bằng người thứ ~i~ vì ta duyệt từ người có tài sản thấp đến cao.
  • Nếu ~cnt <= b_i~ (vì những người được mời trước đó đều đảm bảo có tài sản nhỏ hơn người thứ ~i~) thì người thứ ~i~ sẽ được mời tham gia buổi tiệc: cnt = cnt + 1.

Subtask 3

• Với ~a_i = n~, duyệt từ người thứ ~n~ đến ~1~:
  • Gọi ~cnt~ là số người được mời tham dự buổi tiệc khi duyệt đến người thứ ~i~, nghĩa là ~cnt~ là số người giàu hơn người thứ ~i~ vì ta duyệt từ người có tài sản cao đến thấp.
  • Nếu ~cnt <= a_i~ thì người thứ ~i~ sẽ được mời tham gia buổi tiệc: cnt = cnt + 1.

Subtask 4

• Ta giả sử đáp án của bài là ~x~, nghĩa là ta mời ~x~ người đến buổi tiệc. Ta cần kiểm tra xem có tồn tại ~x~ thỏa mãn hay không?
• Duyệt từ người thứ ~1~ đến ~n~:
  
  • Gọi ~cnt~ là số người được mời tham dự buổi tiệc khi duyệt đến người thứ ~i~ (~cnt~ là số người không giàu bằng người thứ ~i~).
  • Vì số người tham dự buổi tiệc là ~x~ nên số người giàu hơn người thứ ~i~ là ~cnt-x~ vì ta duyệt người có tài sản thấp đến cao.
  • Nếu ~cnt <= b_i~ và ~cnt-x <= a_i~ thì người thứ ~i~ thỏa điều kiện: cnt = cnt + 1.

Code tham khảo

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n;
int a[N], b[N];

bool check(int k) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (k-cnt-1 <= a[i] && cnt <= b[i]) cnt++;
    }
    return cnt >= k;
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    int l = 0, r = n, ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    cout << ans << '\n';

    return 0;
}