poj3232 - Accelerator(加速器)

這個題是我在比賽的時候看到的。

開始的時候，身為菜鳥的我根本沒想到用什麼二分。。。。

後來從别人那裡知道了以後就火速的敲代碼，上交，結果WA。接着我繼續搞代碼，越搞越亂。

弄了好久也沒弄出來

其實是我少了個特判。

那就是k=1的時候。因為k-1做了分母，是以k是不能等于1 的。

由于沒找到弊病，是以我和以為同伴在源代碼的基礎上改了又改，連續交了12遍都沒過。

最後。好吧。我們都放棄了。

第二天等頭腦清醒了，才改掉錯誤終于AC了。

代碼如下：

#include <cstdio>
#include <cmath>
#define M  100010
int a[M], n, k, m, max;
int ok(int ans)
{
    long long cnt = 0;
    for(int i = 0; i < n; i++) if(a[i]>ans)
    {
        int t = ceil(1.0*(a[i]-ans)/(k-1));
        if(t>ans) return 0;
        cnt+=t;
    }
    return cnt<=(long long)ans*m;
}
int solve()
{
   int l = 0, r = max, mid;
   if(k==1) return max;
   while(l<r)
   {
        mid = (r+l)>>1;
        if(ok(mid)) r = mid;
        else l = mid+1;
   }
   return l;
}
int main ()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        max = 0;
        scanf("%d",&n);
        for(int i = 0; i < n; i++) {scanf("%d",&a[i]); max = a[i]>max?a[i]:max; }
        scanf("%d%d",&m,&k);
        printf("%d\n",solve());
    }
    return 0;
}