Trò Chơi Bài (Platinum)

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Hai người chơi A và B cùng chơi một trò chơi bài với $2 N$ lá bài đánh số $1 \dots 2 N$ , mỗi người $N$ lá. Hai người chơi $N$ vòng, mỗi vòng mỗi người đánh một lá bài.

Ban đầu, người đánh lá cao hơn giành 1 điểm. Tuy nhiên, người A có thể chọn một thời điểm để đổi luật: từ đó về sau, người đánh lá thấp hơn giành điểm. Cụ thể:

Không đổi luật: toàn bộ trò chơi theo luật "bài cao thắng".
Đổi sau vòng $k$ ( $1 \leq k \leq N - 1$ ): $k$ vòng đầu dùng luật cao, $N - k$ vòng sau dùng luật thấp.
Đổi ngay từ đầu: toàn bộ theo luật "bài thấp thắng".

Người A biết trước thứ tự bài của B và có thể sắp xếp thứ tự đánh bài của mình tùy ý. Tính số điểm tối đa người A có thể đạt được.

Dữ liệu vào

Dòng 1: số nguyên $N$ ( $2 \leq N \leq 50000$ )
$N$ dòng tiếp theo: lá bài người B đánh ở vòng thứ $i$

Dữ liệu ra

Một số nguyên — số điểm tối đa người A có thể đạt được.

Ràng buộc

$2 \leq N \leq 50000$
Bài của B là $N$ số nguyên phân biệt thuộc ${1, 2, \dots, 2 N}$

Ví dụ

Input	Output	Giải thích
4 1 8 4 3	3	A có bài: 2, 5, 6, 7. Không đổi luật (cao thắng suốt): vòng 1 A đánh 2 > B đánh 1 (+1); vòng 2 A đánh 5 < B đánh 8 (0); vòng 3 A đánh 6 > B đánh 4 (+1); vòng 4 A đánh 7 > B đánh 3 (+1). Tổng: 3 điểm.
10 10 5 8 1 2 3 11 4 16 19	10	Với chiến lược tối ưu, người A giành được tối đa 10 điểm.

Bình luận

Không có bình luận tại thời điểm này.