题解 P6003 【[USACO20JAN]Loan Repayment S】

· · 题解

很明显，可以通过二分x的方式将极值问题转化为判定性问题。
暴力的方法是直接模拟每一天还的牛奶量，复杂度O(k\log n)，能过四个点。
考虑优化二分的判定函数。我们将还的过程分为两部分。前一部分每次还的牛奶量都大于M，后一部分则等于M。
容易发现，在前一部分的某些情况下，会有连续几天还同样的牛奶量。考虑从这个方向去优化复杂度。
设r为未还的奶量，这种情况下连续p天还q加仑。根据题意，q=\dfrac{r}{x}
推式子：

\begin{cases}\left\lfloor\dfrac{r-(p-1)\cdot q}{x}\right\rfloor=q\\\\\left\lfloor\dfrac{r-p\cdot q}{x}\right\rfloor<q\end{cases}

去掉下取整

\begin{cases}\dfrac{r-(p-1)\cdot q}{x}\geq q\\\\\dfrac{r-p\cdot q}{x}<q\end{cases}

整理

\begin{cases}r-p\cdot q+q\geq q\cdot x\\\\r-p\cdot q<q\cdot x\end{cases} \begin{cases}\dfrac{r}{q}-p+1\geq x\\\\\dfrac{r}{q}-p< x\end{cases} \dfrac{r}{q}-x<p\leq\dfrac{r}{q}-x+1

因为p是一个整数，所以p=\left\lfloor\dfrac{r}{q}-x+1\right\rfloor

这样的话，我们就可以一次性算出很多天的还奶量了。后半部分的计算非常简单，直接除一下即可。

复杂度O(\sqrt n\log n)
代码（所有变量的定义与前文相同）

#include<iostream>
#define int long long
using namespace std;
int n,k,m;
bool judge(int x){
    int r=n,d=k;//d是剩余的天数
    while(1){
        int p,q;
        q=r/x;
        if(q<=m){
            return m*d>=r;//处理第二部分
        }
        p=r/q-x+1;
        if(p>d)p=d;//注意天数要在范围之内
        r-=p*q;
        d-=p;
        if(r<=0)return 1;
        if(d==0)return 0;
    } 
}
signed main(){
    cin>>n>>k>>m;
    int l=1,r=n,mid;
    while(l<r){
        mid=(l+r+1)>>1;//这里的二分边界要注意一下
        if(judge(mid))
            l=mid;
        else r=mid-1;
    }
    cout<<l;
    return 0;
}