cccccct_1
2020-12-14 19:20
采纳率: 94.1%
浏览 15

c语言 相差问题?萌新求教

你是一个由n个学生组成的小组的教练。第i个学生的编程技能是a[i]。所有学生都有独特的编程技能。你想把他们以以下的方式分成几个小组:

 

如果两个学生i和j的技能分| a[i]-a[j] |=1,则他们不能属于同一个团队(即同一团队中每对学生的技能差异严格大于1);

 

队伍的数目是要尽可能小

你必须回答与q个问题。

 

输入

输入的第一行包含一个整数q(1≤q≤100)-测试用例数。

 

每个测试用例的第一行包含一个整数n(1≤n≤100)-查询中的学生数。查询的第二行包含n个整数a1,a2,…,an(1≤ai≤100,所有ai都是不同的),其中ai是第i个学生的编程技能。

 

输出

对于每个问题,打印最小团队数量

Example

input

4

4

2 10 1 20

2

3 6

5

2 3 4 99 100

1

42

output

2

1

2

1

第一个测试用例中,有n=4个学生的技能a=[2,10,1,20]。这里只有一个限制:第1名和第3名学生不能在同一个团队中(因为| a1-a3 |=| 2-1 |=1)。可以将他们分成两个小组:例如,学生1、2和4在第一组,学生3在第二组。

 

在第二个测试用例中,有n=2个学生的技能a=[3,6]。可以组成一个包含两个学生的小组。

1条回答 默认 最新

相关推荐 更多相似问题