USACO铜牌 Race (Greedy, Simulation, Binary Search)

#include<bits/stdc++.h>

using namespace std;

//Greedy+binary search

int main(){

ifstream fin("race.in");

ofstream fout("race.out");

int n,k;

fin>>k>>n;

while(n>0){

n--;

int x;

fin>>x;

long long upsum=(long long)(x+1)*x/2;//speed up to x

if(upsum>=k){//x is too large for k

fout<<ceil(sqrt(2*k+0.25)-0.5)<<endl;

continue;

}

int l=0,r=(k-upsum)/x;

if((k-upsum)%x!=0){

r++;

}

while(l<r-1){

int m=(l+r)/2;

int total=k-upsum-x*m;

long long cmax=0;

int up=m/2;

           //greedy increase, but need to decrease to x at beginning of m

if(m%2==0){

cmax=(long long)up*up;

}else{

cmax=(long long)(1+up)*up;

}

           //cout<<n<<" "<<x<<" "<<l<<" "<<r<<" "<<cmax<<" "<<total<<" "<<m<<" "<<up<<endl;

if(cmax>=total){

r=m;

}else{

l=m;

}

}

fout<<x+r<<endl;

}

return 0;

}