【蓝桥杯-筑基篇】贪心

这篇具有很好参考价值的文章主要介绍了【蓝桥杯-筑基篇】贪心。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🍓系列专栏:蓝桥杯

🍉个人主页:个人主页

目录

1.找零问题

①暴力枚举

②贪心

2.人性总是贪婪的

3.堆果子

4.图书推荐


1.找零问题

有币种124510若干张,找零n元,输出找零方案。

①暴力枚举

这是一个找零问题,我们需要找到一种方案,使得用给定的硬币找零时,所需的硬币数量最少。

在这个代码中,我们使用了暴力枚举的思路,即枚举每种硬币的数量,然后判断是否能够凑出目标金额。如果能够凑出目标金额,则输出方案。

这种方法的时间复杂度为 O(n^5),因为我们需要枚举每种硬币的数量,而硬币的种类有 5 种,所以总共需要枚举 5 层循环。

这种方法的优点是代码简单易懂,容易实现。缺点是时间复杂度较高,不适用于大规模数据的处理。

public class A {
    public static void main(String[] args) {
        int[] coins = {1, 2, 4, 5, 10};
        int target = 18;
        int count = 0;
        for (int i = 0; i <= target / coins[0]; i++) {
            for (int j = 0; j <= target / coins[1]; j++) {
                for (int k = 0; k <= target / coins[2]; k++) {
                    for (int l = 0; l <= target / coins[3]; l++) {
                        for (int m = 0; m <= target / coins[4]; m++) {
                            if (i * coins[0] + j * coins[1] + k * coins[2] + l * coins[3] + m * coins[4] == target) {
                                count++;
                                System.out.println("方案" + count + ": " + i + "个1元+" + j + "个2元+" + k + "个4元+" + l + "个5元+" + m + "个10元");
                            }
                        }
                    }
                }
            }
        }
    }
}
方案1: 0个1元+0个2元+2个4元+0个5元+1个10元
方案2: 0个1元+0个2元+2个4元+2个5元+0个10元
方案3: 0个1元+1个2元+4个4元+0个5元+0个10元
方案4: 0个1元+2个2元+1个4元+0个5元+1个10元
方案5: 0个1元+2个2元+1个4元+2个5元+0个10元
方案6: 0个1元+3个2元+3个4元+0个5元+0个10元
方案7: 0个1元+4个2元+0个4元+0个5元+1个10元
方案8: 0个1元+4个2元+0个4元+2个5元+0个10元
方案9: 0个1元+5个2元+2个4元+0个5元+0个10元
方案10: 0个1元+7个2元+1个4元+0个5元+0个10元
方案11: 0个1元+9个2元+0个4元+0个5元+0个10元
方案12: 1个1元+0个2元+3个4元+1个5元+0个10元
方案13: 1个1元+1个2元+0个4元+1个5元+1个10元
方案14: 1个1元+1个2元+0个4元+3个5元+0个10元
方案15: 1个1元+2个2元+2个4元+1个5元+0个10元
方案16: 1个1元+4个2元+1个4元+1个5元+0个10元
方案17: 1个1元+6个2元+0个4元+1个5元+0个10元
方案18: 2个1元+0个2元+4个4元+0个5元+0个10元
方案19: 2个1元+1个2元+1个4元+0个5元+1个10元
方案20: 2个1元+1个2元+1个4元+2个5元+0个10元
方案21: 2个1元+2个2元+3个4元+0个5元+0个10元
方案22: 2个1元+3个2元+0个4元+0个5元+1个10元
方案23: 2个1元+3个2元+0个4元+2个5元+0个10元
方案24: 2个1元+4个2元+2个4元+0个5元+0个10元
方案25: 2个1元+6个2元+1个4元+0个5元+0个10元
方案26: 2个1元+8个2元+0个4元+0个5元+0个10元
方案27: 3个1元+0个2元+0个4元+1个5元+1个10元
方案28: 3个1元+0个2元+0个4元+3个5元+0个10元
方案29: 3个1元+1个2元+2个4元+1个5元+0个10元
方案30: 3个1元+3个2元+1个4元+1个5元+0个10元
方案31: 3个1元+5个2元+0个4元+1个5元+0个10元
方案32: 4个1元+0个2元+1个4元+0个5元+1个10元
方案33: 4个1元+0个2元+1个4元+2个5元+0个10元
方案34: 4个1元+1个2元+3个4元+0个5元+0个10元
方案35: 4个1元+2个2元+0个4元+0个5元+1个10元
方案36: 4个1元+2个2元+0个4元+2个5元+0个10元
方案37: 4个1元+3个2元+2个4元+0个5元+0个10元
方案38: 4个1元+5个2元+1个4元+0个5元+0个10元
方案39: 4个1元+7个2元+0个4元+0个5元+0个10元
方案40: 5个1元+0个2元+2个4元+1个5元+0个10元
方案41: 5个1元+2个2元+1个4元+1个5元+0个10元
方案42: 5个1元+4个2元+0个4元+1个5元+0个10元
方案43: 6个1元+0个2元+3个4元+0个5元+0个10元
方案44: 6个1元+1个2元+0个4元+0个5元+1个10元
方案45: 6个1元+1个2元+0个4元+2个5元+0个10元
方案46: 6个1元+2个2元+2个4元+0个5元+0个10元
方案47: 6个1元+4个2元+1个4元+0个5元+0个10元
方案48: 6个1元+6个2元+0个4元+0个5元+0个10元
方案49: 7个1元+1个2元+1个4元+1个5元+0个10元
方案50: 7个1元+3个2元+0个4元+1个5元+0个10元
方案51: 8个1元+0个2元+0个4元+0个5元+1个10元
方案52: 8个1元+0个2元+0个4元+2个5元+0个10元
方案53: 8个1元+1个2元+2个4元+0个5元+0个10元
方案54: 8个1元+3个2元+1个4元+0个5元+0个10元
方案55: 8个1元+5个2元+0个4元+0个5元+0个10元
方案56: 9个1元+0个2元+1个4元+1个5元+0个10元
方案57: 9个1元+2个2元+0个4元+1个5元+0个10元
方案58: 10个1元+0个2元+2个4元+0个5元+0个10元
方案59: 10个1元+2个2元+1个4元+0个5元+0个10元
方案60: 10个1元+4个2元+0个4元+0个5元+0个10元
方案61: 11个1元+1个2元+0个4元+1个5元+0个10元
方案62: 12个1元+1个2元+1个4元+0个5元+0个10元
方案63: 12个1元+3个2元+0个4元+0个5元+0个10元
方案64: 13个1元+0个2元+0个4元+1个5元+0个10元
方案65: 14个1元+0个2元+1个4元+0个5元+0个10元
方案66: 14个1元+2个2元+0个4元+0个5元+0个10元
方案67: 16个1元+1个2元+0个4元+0个5元+0个10元
方案68: 18个1元+0个2元+0个4元+0个5元+0个10元

②贪心

给定一个需要找零的金额money和一些硬币的面值,计算出最少需要使用多少个硬币才能找零。具体实现是,从大到小遍历硬币面值,每次尽可能使用面值大的硬币,直到找零金额为0为止。在遍历过程中,记录使用的硬币数量和面值,并输出。最后输出使用的硬币数量。

public static void main(String[] args) {
    int[] coins = {10, 5, 4, 2, 1};
    int money = 18;
    // 输出需要找零的金额
    System.out.println("需要找零" + money + "元");

    int count = 0;
    for (int i = 0; i < coins.length; i++) {
        while (money >= coins[i]) {
            money -= coins[i];
            count++;
            // 输出使用的硬币面值
            System.out.println("使用了面值为" + coins[i] + "的硬币");
        }
    }
    // 输出使用的硬币数量
    System.out.println("一共使用了" + count + "个硬币");
}
需要找零18元
使用了面值为10的硬币
使用了面值为5的硬币
使用了面值为2的硬币
使用了面值为1的硬币
一共使用了4个硬币

2.人性总是贪婪的

假如整数n表示当前奖池中已经有的钱的总数,给你一个一夜暴富的机会:请你从n中删除m个数字,余下的数值对应的金额就是你能够拿走的钱,我们知道人性都是贪婪的,那么请编程帮小明使得余下的数字按原次序组成的新数最大,比如当n=92081346718538. m=10时,则新的最大数是9888


样例输入

92081346718538 10
1008908 5

样例输出

9888
98

 主要思路是:从左到右遍历字符串,每次选出当前可选范围内最大的数字,直到选出n-m个数字为止。

n=92081346718538m=10为例 :

例如要保留4位数。

第一位数 ,从下标0到下标10取,  要余3位【下标:11,12,13】

第二位数,要余2位【下标:12,13】

第三位数,要余1位【下标:13】

如下图:

(71条消息) 【蓝桥杯-筑基篇】贪心_热爱编程的小白白的博客-csdn博客,蓝桥杯,java,算法,jvm,数据结构

 具体实现上,程序使用了一个char数组来存储输入的字符串,使用了一个last_select_pos变量来记录上一次选出的数字的位置,以避免重复选取。在每次选取数字时,程序从last_select_pos+1的位置开始遍历,直到可选范围内的最后一个数字,选出其中最大的数字,并更新last_select_pos的值。最后将选出的数字串输出即可。

import java.util.Scanner;

public class selectMoney {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String n = sc.next();// 用字符串的形式读入进来
			int m = sc.nextInt();// 要删除的个数
			int save = n.length() - m;// 保留的个数,删除问题转换成保留的问题
			String max = "";// 存放最后我们选择要保留的字符
			char[] a = n.toCharArray();// n变成字符数组
			int last_select_pos = -1;// 开始的时候一个都没有被选中+1刚好对应0的位置
			for (int i = 1; i <= save; i++) {// 分save次去选择每次可选的最大字符
				char big = '0';// 假定本轮要选的字符是无穷小
				for (int j = last_select_pos+1; j < a.length - (save - i); j++) {
					if (a[j] > big) {
						big = a[j];
						last_select_pos = j;// 记录当前找到的最大的位置
					}
				}
				max = max + big;// 每一次都把找到的可选的最大的字符串追加到尾部
			}
			System.out.println(max);
		}
	}
}

3.堆果子

题目描述:

在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。 多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。

假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。

例如有3种果子,数目依次为1, 2, 9。可以先将1、2堆合并,新堆数目为3,耗费体力为3。
接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12,耗费体力为12。
所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

输入:

(71条消息) 【蓝桥杯-筑基篇】贪心_热爱编程的小白白的博客-csdn博客,蓝桥杯,java,算法,jvm,数据结构

 样例输入

5
1 2 3 4 5

样例输出

33

思路:将数据存入数组内

对数组进行排序,然后将最小的2个值相加【重复此步骤】

5
1 2 3 4 5
------------------------------
[1, 2, 3, 4, 5]
arr[i]:1
arr[i+1]:2
[0, 3, 3, 4, 5]
arr[i]:3
arr[i+1]:3
[0, 0, 4, 5, 6]
arr[i]:4
arr[i+1]:5
[0, 0, 0, 6, 9]
arr[i]:6
arr[i+1]:9
[0, 0, 0, 0, 15]
------------------------------
33
//导入Scanner和Arrays类
import java.util.Scanner;
import java.util.Arrays;

public class A {
	public static void main(String[] args) {
		//创建Scanner对象
		Scanner sc = new Scanner(System.in);
		//读取输入的整数n
		int n=sc.nextInt();
		//创建长度为n的整型数组arr
		int arr[]=new int[n];
		//定义变量number并初始化为0
		int number=0;
		//循环读取n个整数并存入数组arr中
		for (int j = 0; j < arr.length; j++) {
			arr[j]=sc.nextInt();
		}
		//对数组arr进行排序
		Arrays.sort(arr);
		//循环处理数组arr
		for (int i = 0; i < arr.length-1; i++) {
			//将arr[i]和arr[i+1]相加并存入arr[i+1]中
			arr[i+1]=arr[i]+arr[i+1];
			//将arr[i+1]累加到number中
			number+=arr[i+1];
			//将arr[i]赋值为0
			arr[i]=0;
			//对数组arr进行排序
			Arrays.sort(arr);
		}
		//输出number
		System.out.println(number);
	
	}
}

4.图书推荐

本书以“零基础”为起点,系统地介绍了uni-app的跨平台开发与应用。全书内容分为3篇,共12章,具体安排如下。

第一篇:基础篇,包括第1~4章,主要介绍了uni-app的特点和优势、环境搭建、HBuilderX开发工具的安装和使用,以及uni-app的一些基础知识。第二篇:进阶篇,包括第5~9章,主要介绍了uni-app的基础配置、相关组件、导航栏、高效开发技巧,以及uniCloud云开发平台。第三篇:实战篇,包括第10~12章,通过第一个实战,介绍了如何使用uni-app开发小程序;通过第二个实战,介绍了如何使用uni-app进行跨平台开发;通过第三个实战,介绍了如何使用uniCloud云开发。

京东自营购买链接:《uni-app跨平台开发与应用从入门到实践 DCloud/uni-app官方认证教材》

(71条消息) 【蓝桥杯-筑基篇】贪心_热爱编程的小白白的博客-csdn博客,蓝桥杯,java,算法,jvm,数据结构文章来源地址https://www.toymoban.com/news/detail-802268.html

到了这里,关于【蓝桥杯-筑基篇】贪心的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 百日筑基篇——python爬虫学习(一)

    百日筑基篇——python爬虫学习(一) 随着学习的深入,有关从各种不同的数据库中以及互联网上的海量信息,如何有选择性的爬取我们所需的数据以方便我们的数据分析工作,爬虫的学习是必要的。 Python爬虫是指使用Python编程语言编写的程序,通过模拟浏览器行为从网页中

    2024年02月13日
    浏览(49)
  • MySQL筑基篇之增删改查

    ✅作者简介:C/C++领域新星创作者,为C++和java奋斗中 ✨个人社区:微凉秋意社区 🔥系列专栏:MySql一点通 📃推荐一款模拟面试、刷题神器👉注册免费刷题 🔥前言 本文将承接前两篇MySQL专栏的博文,讲解数据库的 增删改查 操作,这里的查询确切的说应该是初级的查询,不

    2024年02月12日
    浏览(52)
  • 算法修炼之筑基篇——筑基一层中期(解决01背包,完全背包,多重背包)

    ✨ 博主: 命运之光​​​​​​ 🦄 专栏: 算法修炼之练气篇​​​​​ 🍓 专栏: 算法修炼之筑基篇 ✨ 博主的其他文章: 点击进入博主的主页​​​​​​ 前言: 学习了算法修炼之练气篇想必各位蒟蒻们的基础已经非常的扎实了,下来我们进阶到算法修炼之筑基篇的

    2024年02月08日
    浏览(32)
  • 蓝桥杯之贪心

    将股票价格的变动抽象成折线图,将每个上升阶段累加起来(每次的累加并不一定代表真实的一次买卖交易,比如两段连续上升的折线,只进行了一次买卖,但对两段上升折线分别累加的收益结果是一致的) 我们设在仓库左边的所有点,到仓库的距离之和为p,右边的距离之和

    2023年04月09日
    浏览(34)
  • 贪心+蓝桥杯

    原题路径 题目思路 : 思路很简单,肯定是贪心做法,要使总代价最小,需用那些出现次数比avg多的数来替换那些没有出现或者是出现次数少于avg的数, 所以我们存当前数每次出现的代价是多少 ,枚举每一个 0 - 9 之间的数 ,如果当前数出现的次数多于avg,那么说明需要减少,

    2024年01月20日
    浏览(65)
  • 蓝桥杯C组-填充-贪心

    点击此处查看原题​​​​​​​ *思路:首先要求 00 11 尽可能的多,所以尽可能多的多配对,配对只在i , i + 1之间发生,所以只需要关注str[i] 和 str[i + 1]即可,如果str[i] == str[i + 1] ,那么一定配对,res ++ , 否则说明只有 str[i] == 0 str[i + 1] == 1 或者 str[i] == 1 str[i + 1] == 0 两种情

    2024年01月18日
    浏览(24)
  • 【蓝桥杯冲冲冲】排队接水--贪心算法巩固 (≧∇≦)

    有 n n n 个人在一个水龙头前排队接水,假如每个人接水的时间为 T i T_i T i ​ ,请编程找出这 n n n 个人排队的一种顺序,使得 n n n 个人的平均等待时间最小。 第一行为一个整数 n n n 。 第二行 n n n 个整数,第 i i i 个整数 T i T_i T i ​ 表示第 i i i 个人的接水时间 T i T_i T i ​

    2024年01月24日
    浏览(42)
  • 【蓝桥杯重点】还不快来学贪心算法!

    【蓝桥杯重点】还不快来学贪心算法! 小 A 有 n n n 个糖果盒,第 i i i 个盒中有 a i a_i a i ​ 颗糖果。 小 A 每次可以从其中一盒糖果中吃掉一颗,他想知道,要让任意两个相邻的盒子中糖的个数之和都不大于 x x x ,至少得吃掉几颗糖。 (ww喜欢在博客里放一些自己喜欢的图,

    2024年01月22日
    浏览(31)
  • 题目 3158: 蓝桥杯2023年第十四届省赛真题-三国游戏(贪心)

    小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵X, Y, Z (一开始可以认为都为 0 )。游戏有 n 个可能会发生的事件,每个事件之间相互独立且最多只会发生一次,当第 i 个事件发生时会分别让 X, Y, Z 增加Ai , Bi ,Ci 。 当游戏结束时 (所有事件的发生与否已经确

    2024年02月01日
    浏览(53)
  • 编程小窍门: 一个简单的go mutex的小例子

    本期小窍门用到了两个组件 mutex 这个类似其他语言的互斥锁 waitGroup 这个类似其他语言的信号量或者java的栅栏锁 示例如下

    2024年02月13日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包