trang chủ / đề bài / exampick

Đề thi

Alice ra một đề thi và tham khảo $n$ bài toán trong thư viện, đánh số từ $1$ tới $n$ ; bài toán thứ $i$ có độ khó $a_{i}$ . Alice chọn ra một tập con các bài (khác rỗng) thỏa mãn:

Phủ: trong $P$ bài liên tiếp bất kỳ phải có ít nhất một bài được chọn.
Tối ưu: trung bình cộng độ khó của các bài được chọn là lớn nhất có thể.

Hãy in ra một cách chọn đạt trung bình lớn nhất.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $P$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

Dòng đầu in số lượng bài được chọn.
Dòng thứ hai in các chỉ số của các bài được chọn theo thứ tự tăng dần.

Nếu có nhiều cách chọn cùng đạt trung bình lớn nhất, in ra cách nào cũng được.

Ràng buộc

$1 < P < n < 10^{5}$
$0 \leq a_{i} \leq 10^{8}$

Ví dụ

Input	Output	Giải thích
8 3 1 2 3 4 5 6 7 8	4 3 6 7 8	Với $P = 3$ , không được để 3 bài liên tiếp nào cùng không được chọn. Chọn các bài 3, 6, 7, 8 (độ khó 3, 6, 7, 8) phủ hợp lệ và cho trung bình $(3 + 6 + 7 + 8) / 4 = 6$ , là lớn nhất.
6 2 10 2 8 2 9 3	3 1 3 5	Với $P = 2$ , không được để 2 bài liên tiếp cùng bị bỏ. Chọn các vị trí lẻ 1, 3, 5 (độ khó 10, 8, 9) là hợp lệ và bỏ được các bài độ khó thấp ở vị trí chẵn, cho trung bình $(10 + 8 + 9) / 3 = 9$ .

Bình luận

skyvn97

đã bình luận 3 months trước

Video giải đề: https://youtu.be/ANKVGawj16E

Lời giải và code mẫu có trong phần mô tả của video

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 7,00một phần

Giới hạn thời gian 1.0s

Python 31.5s

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

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, F#, Forth, Fortran, Go, Groovy, Java, Javascript, Julia, Kotlin, Lean, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, Swift, TCL, Typescript, V, Visual Basic, Zig

Đề bài

Mô tả

Dữ liệu vào

Dữ liệu ra

Ràng buộc

Ví dụ

Bình luận