[CF 506C] Mr. Kitayuta vs. Bamboos

作法：

這題我是完全照著官方詳解的第二種作法寫的，看了很久一直看不懂第一種作法，這裡就紀錄一下大概怎麼實作的。
 在二分搜一個值的時候，一開始所有竹子都同高，只是縮短的速率不一樣。我們可以把所有竹子分成三類，第一類為那些「一直不理他到最後一天高度還是$\geq $他的$h$值」的竹子，我們可以完全不用理他，因為永遠不用把他拉長。至於第二種竹子則是「一直不理他直到最後一天高度會$<$他的$h$值，但不會$<0$」，第三種則是最後一天結束會$<0$的。我們可以先用貪心處理第三種竹子，把他們全部都變第二種之後，剩下的拉長操作的次數就可以依照任意順序對竹子們使用了。貪心的詳細一點來說就是，對每個第三種的竹子都算出「如果一直不理他，那到哪一天他的高度會$<0$」，那麼就只要把他們丟入一個priority_queue中，每次取天恕最小的那跟竹子出來把他拉長，並用一個陣列$num$紀錄每個竹子被拉長了幾次，那麼就可以用$\left \lfloor \frac{h_0+num[i]\cdot p}{a[i]} \right \rfloor+1$算出不理他的話第幾天會$<0$了（其中$h_0$是此次二分搜的值，也是所有竹子的初始高度）。而我的寫法不太一樣，是把第二種和第三種合併處理，也就是一樣都對他們計算上式的值並且丟進priority_queue裡面，只不過所有第二種竹子算出來的值都會$>m$，因為他們在最後一天並不會$<0$，而這也不影響第三種竹子的處理，因為第三種竹子一定會比第二種竹子早出隊，並且保證當 pop 出來的是第二種竹子的時候，所有的第三種竹子都處理完畢了。另外只要再判一下現在被拉長的這個竹子是否已經變成第一種竹子了就好了，如果還沒的話就繼續丟進priority_queue中。當所有程序結束時，priority_queue為空若且唯若此次是成功的。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=100000+10 ;
 
struct P
{
    int id ; LL val ;
    bool operator < (const P &rhs) const
    {
        return val>rhs.val ;
    }
};
 
int n,m,k ;
LL h[maxn],a[maxn],num[maxn],p ;
priority_queue<P> pq ;
bool check(LL h0)
{
    while(!pq.empty()) pq.pop() ;
    memset(num,0,sizeof(num)) ;
    for(int i=1;i<=n;i++) if(h0-a[i]*m < h[i])
        pq.push((P){i,h0/a[i]}) ;
    for(int i=1;!pq.empty() && i<=m;i++)
        for(int _k=1;!pq.empty() && _k<=k;_k++)
    {
        P u=pq.top() ; pq.pop() ;
        if(u.val<i) return 0 ;
        num[u.id]++ ;
        if(h0+p*num[u.id]-a[u.id]*m<h[u.id])
            pq.push((P){u.id,(h0+p*num[u.id])/a[u.id]}) ;
    }
    return pq.empty() ;
}
 
main()
{
    scanf("%d%d%d%lld",&n,&m,&k,&p) ;
    LL l=0 , r=0 ;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&h[i],&a[i]) ;
        l=max(l,a[i]) ;
        r=max(r,h[i]+m*a[i]) ;
    }
    l-- ;
    while(r-l>1)
    {
        LL mid=(r+l)/2 ;
        if(check(mid)) r=mid ;
        else l=mid ;
    }
    printf("%lld\n",r) ;
}