題目鏈接

Problem 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 NN 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 00.Now they want to know the minimum time that Ruins used to pass the last position.

Input

First line contains an integer TT, which indicates the number of test cases.Every test case begins with an integers NN, which is the number of the recorded positions.The second line contains NN numbers a1a1, a2a2, ??, aNaN, indicating the recorded positions.Limits1≤T≤1001≤T≤1001≤N≤1051≤N≤1050<ai≤1090<ai≤109ai<ai+1ai<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

AC

• 題意：一輛汽車每次都是在整點通過關口而且速度是不遞減，問這輛汽車走完所有的路程一共花多長時間？
• 貪心：因為速度保持遞增或者不變，后面的速度越大越好，這樣整體的速度就大、用時也少，當最后一段路程用時為1秒，能符合假設
• 用兩個整數記錄時間和路程，用小數直接處理速度會有精度問題

#include <iostream> #include <cmath> #include <map> #include <vector> #include <set> #include <cstring> #include <queue> #include <algorithm> #define ll long long #define ull unsigned long long #define N 100005 using namespace std;ll a[N]; int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endif int t;scanf("%d", &t);int Case = 1;while (t--) {int n;scanf("%d", &n);for (int i = 1; i <= n; ++i) {scanf("%lld", &a[i]);}// 總時間 ll sum = 1;// 最后一段路程的時間 和 距離 int time = 1, length = a[n] - a[n - 1];// 從后往前模擬 for (int i = n - 2; i >= 0; --i) {ll len = a[i + 1] - a[i];// 時間等于路程除以速度 ll ti = len * time / length;// 如果路程大， 時間加1，滿足速度正向遞增 if (time * len % length) ti++;// 更新當前時間，路程，總時間 time = ti;length = len;sum += ti;}printf("Case #%d: %lld\n",Case++, sum);}return 0; }

總結

以上是生活随笔為你收集整理的HDU Problem - 5935 Car（模拟）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。