20.2.25排位賽D

【題目大意】

一條賽道k(1<=k<=10^9)米長,Bessie在剛開始在位置0,速度為0m/s,每過一秒,它可以提速1m/s,保持目前速度,或者減速1m/s。有N個詢問,求Bessie到達位置k時速度不超過x m/s所要的最短時間。

【解題思路】

先讓Bessie加速到最高速度m再減速到x(如果最高速度未達到x,那就是一直加速到最高速度),假設此時的走過的路程為s,現在來考慮保持勻速的情況,如果k-s<最高速度m,那麼就讓k-s那個速度的時候跑多一秒,此時就是最短時間了。如果k-s>=最高速度m,那相當于用最高速度m再跑（k-s)/m向下取整秒,再用速度（k-s)%m跑一秒。

【代碼】

#include <cstdio>
#include <iostream>
using namespace std;
int j,k,n,len,ans;
bool check(long long x)
{
	long long a=(1+x)*x/2;
	long long b;
	if (x<j) b=0;
	else b=(j+x-1)*(x-j)/2;
	len=a+b;
	if (a+b<=k) return true;
	else return false; 
}
long long find_time()
{
	int l=1,r=1000000;
	while (l<=r)
	{
		int mid=(l+r)/2;
		if (check(mid))
		{
			ans=mid;
			l=mid+1;
		}else r=mid-1;
	}
	bool x=check(ans);
	long long t=ans;
	if (ans>=j) t+=ans-j;
	long long last=k-len;
	if (last!=0)
	{
		t+=last/ans;
		if (last%ans!=0) t++;
	 } 
	return t;
}
int main()
{
	scanf("%d%d",&k,&n);
	for (int i=1;i<=n;i++)
	  {
	  	  scanf("%d",&j);
	  	  long long t=find_time();
	  	  cout<<t<<endl;
	  }
	return 0;  
}