首页 > 代码库 > poj 3232 Accelerator

poj 3232 Accelerator

2024-07-24 10:34:38   220人阅读

http://poj.org/problem?id=3232

题意：有一个含有n辆车的车队，当前距离终点的距离已知，有m个加速器，每个加速器在一个时刻只能给一辆车用，一旦使用就会使得其速度由1变成k，加速器可以重复使用，问最快所有车辆到达终点的时间。

思路：二分枚举所需的最短时间。

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 300000 5 #define ll long long 6 using namespace std; 7  8 ll t,n,m,k; 9 ll a[maxn];10 11 bool ok(ll c)12 {13     ll cnt=0,x=c*m;14     for(int i=0; i<n; i++)15     {16         if(a[i]<=c) continue;17         if((a[i]-c)%(k-1)==0)18         cnt=((a[i]-c)/(k-1));19         else20         cnt=((a[i]-c)/(k-1))+1;21         if(cnt>c) return false;22         x-=cnt;23         if(x<0) return false;24     }25     return true;26 }27 28 29 int main()30 {31     scanf("%lld",&t);32     while(t--)33     {34         scanf("%lld",&n);35         ll max1=0;36         for(int i=0; i<n; i++)37         {38             scanf("%lld",&a[i]);39             max1=max(max1,a[i]);40         }41         scanf("%lld%lld",&m,&k);42         ll l=0,r=max1;43         if(k==1)44         {45             printf("%lld\n",max1);46             continue;47         }48         int mid;49         while(l<r)50         {51             mid=(l+r)>>1;52             if(ok(mid))53             {54                 r=mid;55             }56             else l=mid+1;57         }58         printf("%lld\n",l);59     }60     return 0;61 }
View Code

 

poj 3232 Accelerator


联系
我们