题目大意:
每次操作可以使\(a\)变成\(a+1\)或\(a\cdot k\),问将\(a\)变成\(b\)最少需要几次操作。
将题目等价转化为,将\(b\)变成\(a\)最少需要几次以下操作:
操作1:将\(b\)变成\(b-1\)。
操作2:如果\(b\)能被\(k\)整除,将b变成\(\frac{b}{k}\)。
考虑贪心,当能够使用操作2时优先使用操作2,其余情况使用操作1。具体来说:
- 当\(b\ge a\cdot k\)时,
(1) 如果\(b\)能被\(k\)整除,使用\(1\)次操作2。
(2) 如果\(b\)不能被\(k\)整除,使用\(b-\lfloor\frac{b}{k}\rfloor\cdot k\)次操作1,操作完成后\(b\)可以被\(k\)整除。 - 当\(b<a\cdot k\)时,不能使用操作2(会导致\(b\)小于\(a\)),所以使用\(b-a\)次操作1使\(b\)与\(a\)相等。
#include<bits/stdc++.h>
#define pt printf(">>>")
#define mid (((l)+(r))/2)
using namespace std;
typedef long long ll;
const ll N=1e6+10,inf=1e18+10,mod=1e9+7;
int main(){
int T=1;
cin >> T;
while(T--){
ll a,b,k,ans=0;
cin >> a >> b >> k;
while(a<b){
if(b>=a*k){
if(b%k==0)b/=k,ans++;
else ans+=b-b/k*k,b=b/k*k;
}else ans+=b-a,b=a;
}
cout << ans << endl;
}
return 0;
}
标签:cdot,ll,ans,操作,整除,CodeChef,Change,贪心
From: https://www.cnblogs.com/alric/p/18208207