喝咖啡

咖啡"/>

喝咖啡

题目

X很喜欢喝咖啡但是别人告诉他经常喝咖啡不好，X决定限制自己喝咖啡的间隔天数不小于K。但是每月（按30天计）有某些日子一定要喝咖啡，求X一个月最多能喝多少天咖啡。

输入：

第一行为样例数，接下来每两行代表一个样例，样例中的第一行两个正整数K、M分别表示喝咖啡的间隔天数和每个月一定要喝的日子的天数；

第二行表示需要喝咖啡的日期，日期之间用空格分隔。

输出：最多能喝咖啡的天数。

样例:

输入：

4

0 10

1 2 3 4 5 6 7 8 9 10

1 15

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29

1 7

5 9 13 17 21 25 29

1 0

 

输出：

30

15

15

15

说明：第二行0 10，分别表示至少间隔0天可以喝咖啡，其中有10天一定要喝，日期分别是第二行的十个数，输出结果30表示一个月最多有30天可以喝咖啡（间隔0天就是天天都可以喝啦~~）

分析

1、特殊情况：如果间隔天数K=0，直接输出30；

2、正常情况：间隔天数K>0:

首先，我们知道，可以喝咖啡的天数res>=M ( M是题中给出的一定会喝的天数，且保证满足条件间隔K天 )

那么现在，我们要解决的问题是，一定要喝咖啡的两个日期中间，还有多少天可以和咖啡呢？

比如第三个样例，间隔天数K=1，5号和9号之间，只有7号一天满足条件，所以 此时，res=7+1=8；

9号和13号之间，只有11号一天满足条件，所以 res=8+1=9；

...

我们只要算出每两个数中间可以插入多少个数，就可以了。

穷举我当然知道啦，那怎么算嘛？--来，坐下~

算法

样例，输入：

1 7

5 9 13 17 21 25 29

输出：

15

①一开始，我们就知道可以喝咖啡的天数res>=7=M,题目都给了嘛，这就不用算了，肯定要喝的嘛。

②怎么算可以在两个数之间插入的个数呢？举例，5 和9：

5_ _ _9

我们可以知道，间隔1天可以喝咖啡，则，每2天最多可以喝一次，5号到9号是9-5=4天，5号喝了，所以，6,7,8,9号四天中，有4/2=2天（即7号和9号）可以喝咖啡，但是，9号我们在最上面就算过了（最开始res=M时，就包含了数组中原有的9号），所以少算一天，res +=(9-5)/(1+1)-1=1，即 res +=(arr[i+1]-arr[i])/(K+1)-1天，此时，res =7+1=8

③9和13之间也一样，9_ _ _ 13,也是res +=(13-9)/(1+1)-1=1,res=8+1=9

...

一直算到25和29之间，此时res = 13.(给出的数组+[7,11,15,19,23,27]这六天）

④咦？答案不是15吗？是的，别忘了，还有1-4号和30号我们还没考虑。

其中，29号喝了咖啡，30号就不能喝了。

1-4号呢？我们知道，1和3号是满足条件可以喝咖啡的。res = 13 +2=15,就是答案。

那么，2是怎么来的呢？

原理相同，1-4号之间可以喝咖啡的天数day= (5-1)/(1+1)=(arr[0]-1)/(K+1)=2，这里需要减1吗？--不需要

what ？？？为什么？？？？？因为上面9号我们都在最初的数组中计数了，而这里1,3号，数组中都没有出现过。

其实，29号到月末也是一样的原理，day= (30-29)/(1+1)=(arr[0]-1)/(K+1)=0,如果有31号，那么，day = day= (31-29)/(1+1)=1,恩，31号的确可以喝咖啡，当然，这里题目说没有31号。

代码如下：

import java.util.Scanner;
public class Main {public static void main(String args[]) {Scanner sc = new Scanner(System.in);int T = Integer.parseInt(sc.nextLine());for(int i=0;i<T;i++){int K = sc.nextInt();int M = sc.nextInt();sc.nextLine();//天数K==0if(K==0){System.out.println(30);}else{int res = M;String[] ss = sc.nextLine().split(" ");int [] arr = new int[ss.length];for(int j=0;j<M;j++){arr[j] = Integer.parseInt(ss[j]);}int start = 1 , end ;for(int j=0;j<M;j++){end =arr[j];res += new Main().count(start,end,K);start = end;}//单独算最后一个一定要喝咖啡的日期到30号的天数res += (30-start)/(K+1);System.out.println(res);}	}}//计算两个日期之间有多少天可以喝咖啡public int count(int start, int end, int k){if(start>=end)return 0;//兼容了从1号开始到第一个一定要喝咖啡的日期return (end-start)/(k+1)+(start==1?0:-1);}
}

说明

为什么我们计算 从1号开始到第一个一定要喝咖啡的日期 之间的天数和其他情况合并，而要单独计算 最后一个一定要喝咖啡的日期到30号的天数 不合并呢？头和尾的情况不是一样的吗？

是的，但是，arr里可能没有30号呀，so，end可能永远都不等于30。所以我们自力更生，计算一下就可以啦~~