首页 > 其他分享 >【CodeChef】Change A to B(贪心)

【CodeChef】Change A to B(贪心)

时间:2024-05-23 13:19:13浏览次数:20  
标签:cdot ll ans 操作 整除 CodeChef Change 贪心

题目大意:

每次操作可以使\(a\)变成\(a+1\)或\(a\cdot k\),问将\(a\)变成\(b\)最少需要几次操作。


将题目等价转化为,将\(b\)变成\(a\)最少需要几次以下操作:
操作1:将\(b\)变成\(b-1\)。
操作2:如果\(b\)能被\(k\)整除,将b变成\(\frac{b}{k}\)。

考虑贪心,当能够使用操作2时优先使用操作2,其余情况使用操作1。具体来说:

  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\)整除。
  2. 当\(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

相关文章

  • WPF插件之 - PropertyChanged.Fody使用详解
    总目录文章目录总目录一、PropertyChanged.Fody是什么?二、PropertyChanged.Fody的安装三、PropertyChanged.Fody的功能1.特性1实现属性通知的功能2通知其他属性4不进行属性通知3指定属性更改时将调用的方法5设置当前属性依赖的属性6不检查是否相等7DoNotSetChangedAttribu......
  • 反悔贪心
    1.介绍贪心:即考虑局部最优解达到全局最优解的目的,但有时局部最优解并不会达到全局最优解,此时有两种思考方向,dp和反悔贪心dp:能全局计算答案,根据拓扑学的DAG实现状态转移达到最优(这里不过多介绍)反悔贪心:根据之前的决策进行反悔操作,主要用反悔堆实现去除性价比最低的决策,达到......
  • 反悔贪心学习笔记
    本文仅用于笔者关于反悔贪心的学习笔记,反悔贪心是笔者在一场$div4$中遇到的问题,故来学习一番【学习笔记】反悔贪心 1、什么是反悔贪心?贪心本身是没有反悔操作的,贪心求的就是当前的最优解。但当前的最优解有可能是局部最优解,而不是全局最优解,这时候就要进行反悔操......
  • [ES2024] Simplify array immutable changes with the new array.with method
    Thenew Array.with methodgivesyouanimmutablesyntaxforchangingvaluesofanarrayataspecifiedindex.Sometimes .map willbemoreefficient.So,inthislessonwe'llcomparebothmethodswhilereplacinganobjectataspecificindex. varto......
  • 518_coins_changeII_找零钱II
    问题描述链接:https://leetcode.com/problems/coin-change-ii/Youaregivenanintegerarraycoinsrepresentingcoinsofdifferentdenominationsandanintegeramountrepresentingatotalamountofmoney.'Returnthenumberofcombinationsthatmakeupthat......
  • 挑战程序设计竞赛 2.2章习题 POJ - 3617 Best Cow Line 贪心
    FJ正准备带着他的N头奶牛(1≤N≤2,000)参加一年一度的“年度最佳农民”比赛。在这个比赛中,每个农民都会将他的奶牛排成一行,然后引导它们经过评委。今年比赛的组织者采用了一种新的注册方案:只需按照它们出现的顺序注册每头奶牛的首字母(即如果FJ带着Bessie、Sylvia和Dora依次出......
  • 使用Spring HttpExchange时数据对象遇LocalDateTime字段类型json反序列化失败的解决方
    方法:重写MessageConverter,使得yyyy-MM-ddHH:mm:ss的字符串能反序列化到LocalDateTime类型上。@ConfigurationpublicclassHttpClientConfig{@Value("${service.host}")privateStringhost;@BeanRestClient.BuilderrestClientBuilder(){r......
  • 使用SaveChanges()更新数据库失败
    item.ModelType=TestCase.ModelType;item.TestType=TestCase.TestType;item.TestCaseType=TestCase.TestCaseType;item.TestCaseName=TestCase.TestCaseName;item.TestDescribe=TestCase.......
  • 322 - Coin Change 换零钱
    问题描述Youaregivenanintegerarraycoinsrepresentingcoinsofdifferentdenominationsandanintegeramountrepresentingatotalamountofmoney.Returnthefewestnumberofcoinsthatyouneedtomakeupthatamount.Ifthatamountofmoneycannotbe......
  • 【CodeChef】Prison Escape(最短路)
    题目大意:给出一个01矩阵,求每个0移动(每次可以向有公共边的格子移动一步)到矩阵边界至少要经过多少个1。考虑建最短路模型,将矩阵中的每个位置拆分为入点和出点,矩阵外部设为一个点。枚举矩阵中的每个位置:如果这个位置在矩阵边界,矩阵外部向这个位置的入点连一条长度为0的边。......