1000ms

Difficulty: 5

所属公司 : 荣耀

时间 :2025年10月19日

算法与标签>贪心算法

会员或题库专享

请先，开通会员或购买题库荣耀机考编程题库，可解锁完整内容。

购买荣耀机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（荣耀机考编程题库），可解锁完整内容。

购买题库开通会员

解题思路

目标是把全部学生分成若干行，每行是严格递增的等差数列，且列数 $N$ 最大。
正确思路：直接“面向 $N$ ”检查可行性，而不是让每行随意变长。做法是对 $N$ 从大到小枚举，检查能否把所有人恰好分成若干条长度恰为 $N$ 的等差序列（不同序列的公差可不同）。
可行性检查（贪心构造）：
1. 复制频次表 cnt；每次取当前最小未用身高 a 作为一行的起点；
2. 枚举候选第二个元素 b>a（只从当前还有剩余的高度中挑），设公差 d=b-a，验证序列 {a, a+d, ..., a+(N-1)d} 是否都还各至少有 1 个；若可以，则扣减这些元素的计数，记为一行；

题目内容

某所学校校庆活动，需要将学校学生编排一个方阵。方阵要求:分成 $K$ 行， $N$ 列，每行的同学身高(为整数,如 $160$ )都成一个递增的等差数列，并且使得 $N$ 最大。

约束:

人数 $<= 1000$ 人