T392022 破自行车 的题解

Tis员工 · 2025-02-22 16:45:32 · 个人记录

分类讨论题？预估是个橙题或黄题罢。

分解一下是要走两段路，一段为水平方向上长度为 a 的路，另一段是竖直方向上长度为 b 的路。

先考虑不要冲出去，这时候尽可能省的话水平方向与竖直方向分别需要的使用次数为：

然后开始分类讨论：

• k_a+k_b\ge k

这说明自行车可使用的次数不足以或刚好支持我们如此节省。这个情况下的答案为：

• k_a+k_b=k-1

这说明破旧的自行车足以支持我们如此节省，甚至还能多出来一次机会。这时需要再次讨论：

• • 不使用这个多出来的机会。

可得答案为：

• • 在水平方向上使用这个多出来的机会。

由于该市区面积巨大，跑到哪里都可以，所以我们可以冲出水平方向原来需要走的距离再走回来，说不定可以少走几步路。

其中 a\%l 表示 a 除以 l 所余下的余数。

• • 在竖直方向上使用这个多出来的机会。

可得答案为：

综上，第二个情况的答案为上面三个表达式的最小值

• k_a+k_b\le k-2

这时候多出来至少两个使用次数。依旧仿照第二个情况进行分类。需要注意到的是，同一方向上不可能使用两个及以上的多出来的骑行机会，这样只会冲出去更远，需要走更多得到路。比较简单，这里不再赘述，可以直接阅读代码。

这样就完成了吗？并不是的。上面一系列分类讨论是建立在 k_a 与 k_b 有意义的情况下。所以还需要单独讨论 l=0 的情况。这时需要走 (a+b) 的距离。

整道题还是很清晰的，代码写起来也不麻烦，就这样。

完整代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9){write(x/10);}
    putchar((x%10)+48);
}
int t,a,b,l,k,tmp1,tmp2,res1,res2,res3; 
signed main(){
    t=read();
    for(int o=1;o<=t;o++){
        a=read();b=read();k=read();l=read();
        if(l==0){
            write(a+b);
        }else{
            tmp1=(int)a/l;tmp2=(int)b/l;
            if(tmp1+tmp2>=k){
                write(a+b-k*l);
            }
            else if(tmp1+tmp2==k-1){
                res1=a+b-(tmp1+tmp2)*l;
                res2=res1-(a%l)+(l-(a%l));
                res3=res1-(b%l)+(l-(b%l));
                write(min(min(res2,res3),res1));
            }
            else{
                res1=a+b-(tmp1+tmp2)*l;
                res2=res1-(a%l)+(l-(a%l));
                res1=min(res1,res2);
                res3=res1-(b%l)+(l-(b%l));
                res1=min(res1,res3);
                write(res1);
            }
        }
        putchar('\n');
    }
    return 0;
}