trang chủ / bài tập / maxteams

Lập đội tối đa

Đề bài

Mô tả

n lập trình viên, người thứ i có kỹ năng ai. Bạn muốn chia họ thành một số đội (mỗi đội không rỗng) sao cho số đội lập được là lớn nhất.

Mỗi đội phải thoả điều kiện: số lượng thành viên trong đội nhân với kỹ năng nhỏ nhất trong số các thành viên của đội phải không nhỏ hơn x.

Mỗi lập trình viên thuộc về nhiều nhất một đội. Một số lập trình viên có thể không thuộc đội nào.

Hãy tính số đội tối đa có thể lập được.

Dữ liệu vào

  • Dòng đầu chứa số nguyên t, số lượng bộ dữ liệu.
  • Với mỗi bộ dữ liệu:
    • Dòng đầu chứa hai số nguyên nx, số lượng lập trình viên và giá trị ràng buộc.
    • Dòng thứ hai chứa n số nguyên a1,a2,,an.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên là số đội tối đa có thể lập được.

Ràng buộc

  • 1t1000
  • 1n105
  • 1x109
  • 1ai109
  • Tổng của n trên tất cả các bộ dữ liệu không vượt quá 105.

Ví dụ

Input Output Giải thích
3
5 10
7 11 2 9 5
4 8
2 4 2 3
4 11
1 3 3 7
2
1
0
Bộ 1: đội {11} có 1×1110, đội {7, 9} có 2×710, được 2 đội. Bộ 2: cả 4 người tạo 1 đội 4×2=88. Bộ 3: không lập được đội nào.
3
6 6
3 3 3 3 3 3
5 1
1 1 1 1 1
3 1000000000
1000000000 1000000000 1000000000
3
5
3
Bộ 1: mỗi 2 người tạo 1 đội (2×36), được 3 đội. Bộ 2: x=1 nên mỗi người là một đội. Bộ 3: mỗi người kỹ năng 109 tự tạo một đội.

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