<span>HDU5935 Car（精度水题）</span>
题意：
给你一些递增的正整数点，让你从0开始沿着这些点走
之间速度不能下降，然后任意两点间的时间是整数
思路：
最后一段肯定是1分钟过的，然后就有了初始速度，向前推就可以了
但是用double存的速度结果就喜闻乐见了，改成分数就过了
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <stack> #include <map> #include <string> #include <time.h> #include <cmath> #include <stdlib.h> #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define ou(a) printf("%d\n",a) #define pb push_back #define mkp make_pair template<class T>inline void rd(T &x) { char c=getchar(); x=0; while(!isdigit(c))c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); using namespace std; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int N=1e5+10; int t,n,a[N]; int main() { #ifndef ONLINE_JUDGE //IN #endif int cas=0; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); LL ans=1; LL zi=a[n]-a[n-1],mu=1; for(int i=n-1;i>=1;i--) { LL d=a[i]-a[i-1]; if(zi>d*mu) { mu=1; zi=d; ans++; } else if(d*mu%zi==0) ans=ans+d*mu/zi; else { LL t=d*mu/zi+1; int tmp=__gcd(d,t); zi=d/tmp; mu=t/tmp; ans=ans+t; } } printf("Case #%d: %lld\n",++cas,ans); } return 0; }
