OpenJudge

G:智障蛇大作战

总时间限制:
3000ms
内存限制:
65535kB
描述

贪吃蛇最近产生了一条变种蛇,名叫智障蛇。由于是变种,智障蛇的头部变得特别坚硬,不再怕撞到蛇,反而因为头部坚硬,能把其他贪吃蛇撞成两段,撞击位置

由你决定(只能将贪吃蛇撞成两段长度均为整数)。

被撞的贪吃蛇从被撞处分成两段。长度小于智障蛇的那段将消失,长度大于或等于智障蛇的那段则继续存在。

没有被撞的贪吃蛇,即便长度小于智障蛇,也不会消失。

作为奖励,贪吃蛇每消失一段智障蛇长度加1。

(注意若撞断后两段都比智障蛇短,则两段都消失,智障蛇长度+2。两段都比较长度后才做奖励判定)

现在智障蛇进入了贪吃蛇大作战游戏中,智障蛇想通过最少的撞击次数把其他蛇消灭。

由于智障蛇比较智障,不知道最少要撞多少次,所以还请机智的你告诉智障蛇它最少的撞击次数。

输入
输入保证所有数都是正整数
首先输入一个数T(1 <= T <= 10)代表有T组测试数据。
对于每组测试数据
第一行一个数L( 2 <= L <= 10000),N(1 <= N <= 10000),L代表智障蛇的初始长度,N代表贪吃蛇的个数
第二行有N个数,表示N个贪吃蛇的长度Ai。(2 <= Ai <= 1000000)
输出
对于每组测试数据,输出所需最少撞击次数
样例输入
2
2 3
2 3 4
2 4
3 3 6 6
样例输出
3
5
提示
样例解释
第一组样例
撞击对象(编号) 自身长度 撞击次数
1 4 1
2 6 2
3 8 3
第二组样例
撞击对象(编号) 自身长度 撞击次数
1 3 1
1 5 2
2 7 3
3 9 4
4 11 5
第一次撞一号贪吃蛇时,将1号撞成1,2两段,自身为2,故长度只加1
且1号贪吃蛇长度为1的那段消失,长度为2的继续存在
来源
汤泽川
全局题号
13319
提交次数
11
尝试人数
3
通过人数
1