Nhóm thám hiểm

Đề bài

Mô tả

N nhà thám hiểm trẻ chuẩn bị đi khám phá rừng. Mỗi nhà thám hiểm thứ i có một chỉ số thiếu kinh nghiệm ei là một số nguyên dương.

Trưởng đoàn muốn chia họ thành các nhóm để đi khám phá. Một nhà thám hiểm có chỉ số thiếu kinh nghiệm e chỉ đồng ý tham gia vào một nhóm có từ e người trở lên (kể cả bản thân người đó).

Không bắt buộc phải xếp mọi nhà thám hiểm vào nhóm, một số người có thể ở lại lều. Mỗi người chỉ thuộc tối đa một nhóm.

Hãy tìm số nhóm nhiều nhất có thể thành lập.

Dữ liệu vào

  • Dòng đầu chứa số lượng bộ dữ liệu độc lập T.
  • Với mỗi bộ dữ liệu:
    • Dòng đầu chứa số nguyên N: số nhà thám hiểm.
    • Dòng thứ hai chứa N số nguyên e1,e2,,eN.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số nhóm nhiều nhất có thể thành lập.

Ràng buộc

  • 1T2·105
  • 1N2·105
  • 1eiN
  • Tổng N trên tất cả các bộ dữ liệu không vượt quá 3·105.

Ví dụ

Input Output Giải thích
2
3
1 1 1
5
2 3 1 2 2
3
2
Bộ 1: mỗi người có ei=1 nên tự thành một nhóm, được 3 nhóm. Bộ 2: nhóm gồm 3 người {1,2,3} và nhóm gồm 2 người {2,2}, được 2 nhóm; người còn lại ở lại lều.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0