题目

Description

Ruins is driving a car to participating in a programming contest. As on a very tight schedule, he will drive the car without any slow down, so the speed of the car is non-decrease real number.

Of course, his speeding caught the attention of the traffic police. Police record N positions of Ruins without time mark, the only thing they know is every position is recorded at an integer time point and Ruins started at 0.

Now they want to know the minimum time that Ruins used to pass the last position.

Input

First line contains an integer T, which indicates the number of test cases.

Every test case begins with an integers N, which is the number of the recorded positions.

The second line contains N numbers a1, a2, , aN, indicating the recorded positions.

Limits
1≤T≤100
1≤N≤10⁵
0<ai≤10⁵
ai<ai+1

Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the minimum time.

Sample Input

1
3
6 11 21

Sample Output

Case #1: 4

题解

对于一群坐标数据,不知道每一个数据的时间,并且可知速度是递增的,求可能的最小时间

要使时间最小,尽可能使速度最大即可
对于最后一个区间,显然 1s 是最优解,这样就确定了最后一个区间的速度

然后对于前一个区间,就是求在不超过这个速度的情况下的最大速度(最小时间),直接用区间除以最大速度向下取整即可
然后递推可算出所有区间

也即: 求出各个区间除以该区间限制条件(向下取整)的和

严格证明的贪心算法,应该能秒出思路
一遍 A

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <vector>
#include <list>
#include <map>
#include <functional>

using namespace std;

const int maxn = 100005;

int kase = 1;
int a[maxn];

int vs_main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    a[0] = 0;

    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;

        long long sum = 0;
        for(int i = 1;i <= n;i++)
            cin >> a[i];

        double maxv = 99999999;
        int ans = 0;
        for(int i = n;i>0;i--) {
            int dis = a[i] - a[i - 1];
            double tt = (double)dis / maxv;
            int t = (int)(tt + 0.001);
            if((double)dis / (double)t > maxv)
                t++;

            maxv = (double)dis / (double)t;
            ans += t;
        }
        cout << "Case #" << kase++ << ": " << ans << endl;

    }
    return 0;
}