锐客网

  1. 首页 > it技术 > >

13届蓝桥杯夺奖冲刺营|蓝桥杯省赛夺奖冲刺营贪心算法

java蓝桥杯算法

蓝桥杯省赛夺奖冲刺营贪心算法 「找零问题」
题目描述
蓝桥商店的老板需要找零 n 元钱。
钱币的面额有：100 元、50 元、20 元、5 元、1 元，问如何找零使得所需钱币的数量最少？
注意：n 可能为 0，也能为几百元（别问，问就是来着里微信提现来了）
输入描述
在第一行给出测试例个数 N，代表需要找零的钱数。
1≤N≤105
输出描述
输出共有 5 行，每一行输出数据输出找零的金额与数量，详情看样例。
示例
输入

365

输出
100:3 50:1 20:0 5:3 1:0

运行限制
最大运行时间：1s
最大运行内存: 128M
【13届蓝桥杯夺奖冲刺营|蓝桥杯省赛夺奖冲刺营贪心算法】代码
import java.util.Scanner; public class Main { static int[] m= {100,50,20,5,1}; static int n; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n=sc.nextInt(); //钱 for (int i = 0; i < m.length; i++) { System.out.println(m[i]+":"+n/m[i]); n-=n/m[i]*m[i]; } } }

「小 B 的宿舍」
题目描述
小B的宿舍楼沿着走廊南北向的两边各有200 个房间，如下所示：
[房间1][房间3][房间5][房间7][房间9 ]...[房间399] ---------------------------------------------- 走廊 ---------------------------------------------- [房间2][房间4][房间6][房间8][房间10]...[房间400]

最近，由于转专业和专业分流的原因，宿舍将迎来新的调整，以便组成新的班级后方便管理。
但是由于走廊狭窄，走廊里只能通过两个搬运的物品（可以同向也可以反向），因此必须指定高效的搬运计划。
老师给了每位同学下达了以下要求，让同学们体现收拾好行李，然后给每位同学 1 分钟的时间搬运。
当从房间 i 搬运行李到 j 时，i 与 j 之间的走廊都会被占用，但是可以容纳两个不同同学同时搬运。所以，10 分钟之内同一段走廊最多两个人同时搬运，不重叠的走廊也可以同时搬运。
小B的老师是个数学老师，经过运筹学一通计算他得到了最优的搬运计划。
虽然计划不唯一，但是最优值唯一，请问这个最短时间是多少？
输入描述
输入数据有 T 组测试例，在第一行给出测试例个数 T。
每个测试例的第一行是一个整数 N（1≤N≤200)，表示要搬运行李的人数。
接下来 N 行，每行两个正整数 s 和 t，表示一个人，要将行李是从房间 s 移到到房间t。
输出描述
每组输入都有一行输出数据，为一整数 Time，表示完成任务所花费的最小时间。
示例
输入
3 4 10 20 30 40 50 60 70 80 2 1 3 2 200 3 10 100 20 80 30 50

输出
10 10 20

运行限制
最大运行时间：1s
最大运行内存: 128M
代码
import java.util.Arrays; import java.util.Scanner; public class Main { static int[] m=new int[201]; static int T; public static void main(String[] args) { Scanner sc = new Scanner(System.in); T=sc.nextInt(); //测试数 int n,l,r,max=0; while(T-->0) { n=sc.nextInt(); //人数 while(n-->0) { l=sc.nextInt(); r=sc.nextInt(); for (int i = l; i <= r; i++) { m[i]+=1; } } max=0; for (int i = 1; i <= 200; i++) { if(m[i]>max)max=m[i]; } System.out.println((max+1)/2*10); Arrays.fill(m, 0); } } }

「贪心的自助餐」
题目描述
小B同学想去吃自助餐，但是他是那种比较节俭的的人，既不想浪费食物，又想尽可能吃的贵一点，他于是私下里做了调查。
小蓝餐厅的自助餐有 n 种食材，每种食材都有它的价格。
而且也能估计出每一份的重量，所以他列了一个表格：
菜品 价格（元） 重量（g）
红烧牛肉 30 300
油闷大虾 8 5
四喜丸子 4 8
三文鱼 5 3
排骨 18 200
麻辣兔头 20 120
高汤海参 40 70
扇贝粉丝 8 32
牛排 79 240
小B的饭量为 C(g)，他想知道在不超过饭量的情况下他最多能吃多少钱的菜品。
请你设计一个程序帮助小B计算他的最多吃了多少钱。（假设自助餐厅的菜品供应同样的菜品每个人只能取一份。）
输入描述
第一行输入两个整数 n,C（0≤n≤103 ，0≤C≤104），其中 n 为菜品数量，C 为小B的肚子容量。
接下来 n 行每行输入两个数 v[i],w[i]，v[i] 是第 i 个菜品的价值，w[i] 表示第 i 个菜品的重量（0≤v[i],w[i]≤104）。
输出描述
输出一行数据，表示最大的价值，保留小数点后三位数。
示例
输入
20 1000 1 22 2 43 123 214 12 2 123 432 21 223 22 16 77 49 34 78 34 9 43 677 21 34 23 23 12 56 332 56 21 99 123 545 389 33 12 999 23 88

输出
1204.114

运行限制
最大运行时间：1s
最大运行内存: 128M
代码
import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main { static Food[] m; static int n; static double c; static class Food{ double v; double w; double avg; public Food(double v,double w) { this.v=v; this.w=w; } } static class MyComp implements Comparator{ @Override public int compare(Food o1, Food o2) { if(o1.avg

    推荐阅读


    上一篇：蓝桥杯单片机|蓝桥杯单片机 省赛 第13届模拟题

    下一篇：13届蓝桥杯夺奖冲刺营|蓝桥杯省赛夺奖冲刺营散列表篇