题目描述

巴克特计划乘坐巴士来一场穿越乡间的漫长旅行。

她在旅途之中，一共需要搭乘N条巴士路线，这些路线按必须乘坐的顺序从1到N编号。

巴士速度很快，但是班次并不频繁。

第i条巴士路线每$ X_i $天运行一次。

更具体地说，她只能在第$ X_i,2X_i,3X_i… $天乘坐第i条巴士路线。

由于巴士速度很快，她可以在同一天乘坐多辆巴士。

巴克特必须在D天之内完成旅行，但她想尽可能晚的开始旅行。

请问在确保D天内完成旅行的情况下，她最晚可以在第几天搭乘第一班巴士。

保证巴克特可以在D天内完成旅行。

输入格式

第一行包含整数T，表示共有T组测试数据。

对于每组测试数据，第一行包含两个整数N和D。

第二行包含N个整数，第i个是 $X_i$。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为Case #x: y，其中x为组别编号（从 1 开始），y 为她乘坐第一班车的最晚天数。

数据范围

$ 1≤T≤100$,
$ 1≤Xi≤D $,
$ 1≤N≤1000 $,
$1≤D≤10^12 $

样例

输入样例：

3
3 10
3 7 2
4 100
11 10 5 50
1 1
1

输出样例：

Case #1: 6
Case #2: 99
Case #3: 1

算法1

(贪心) $O(n)$

• 根据题意要尽量晚的去乘车，所以我们就可以贪心的去考虑让最后一辆车最晚可以什么时候做

• 求解公式为 d = (d / x) * x。 d为规定天数，x为该车的周期

• 在此基础上依次递推下去便为最优解

• 注意该题目long long 范围。

时间复杂度

循环一次，复杂度O(n)

参考文献

Google KickStart

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;

const int N = 1010;

LL n, d;
LL x[N];

int main()
{
    int T;
    cin >> T;
    int cnt = 1;
    while(T --){
        cin >> n >> d;
        for(int i = 0; i < n; i++) cin >> x[i];

        for(int i = n - 1; i >= 0; i --){
            d = (d / x[i]) * x[i];
        }

        printf("Case #%d: %ld\n", cnt ++, d);
    }
    return 0;
}