题解 P6746 【Operations】

## 题目大意 有两个非负整数 $a,b$ 。现有两种操作。 - $a\gets a-x,b\gets b-x$ ，其中 $x$ 为正整数。此操作花费非负整数 $c$ 。 - $a\gets a\times x,b\gets \left\lfloor\dfrac{b}{x}\right\rfloor$ ，或者 $b\gets b\times x,a\gets \left\lfloor\dfrac{a}{x}\right\rfloor$ ， 其中 $x$ 为正整数。此操作花费非负整数 $d$ 。 询问将 $a,b$ 都变成 $0$ 所花费的最大权值。 ## 题解 一道挺有意思的分类讨论题。 - 当 $a=b=0$ 时，显然答案为 $0$ 。 - 当其中一个为 $0$ 时，我们可以执行操作 $2$ ， $x$ 取一个很大的值。此时另外一个非零的元素就能通过除法变成 $0$ 。 - 当两者都不为 $0$ 时，又存在三种情况。 - 当 $a=b$ 时 ，我们可以仅使用一次操作 $1$ 。 - 使用操作 $1$ 将更小的那个数减到 $0$ 。另外一个数就可以使用一次操作 $2$ 变成 $0$ 。 - 使用两次操作 $2$ 。先将某个数除成 $0$ ，再将另外一个数除成 $0$ 。 一个公式概括答案： $$ans=\begin{cases} 0 & a=b=0 \cr d & a\times b=0 \text{ 且 } a+b\neq 0 \cr \min\{c,2\times d\} & a=b\neq 0 \cr \min\{c+d,2\times d\} & \text{其他情况} \end{cases}$$ ## 参考代码 ```cpp #include<bits/stdc++.h> #define up(l,r,i) for(int i=l;i<=r;i++) #define dn(l,r,i) for(int i=l;i>=r;i--) using namespace std; typedef long long LL; const int INF =2147483647; int qread(){ int w=1,c,ret; while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0'; while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0'; return ret*w; } int a,b,c,d,ans=INF; int main(){ a=qread(),b=qread(),c=qread(),d=qread(); ans=min(ans,c+d); if(a==b) ans=min(ans,c); if(a==0||b==0){ ans=min(ans,d); } ans=min(ans,2*d); if(a==0&&b==0) ans=0; printf("%d\n",ans); return 0; } ```