贪心算法 - 信奥网|信息学奥赛

0推荐

807浏览

信息学奥赛一本通T1320：贪心算法均分纸牌

【题目描述】有n堆纸牌，编号分别为 1，2，…, n。每堆上有若干张，但纸牌总数必为n的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1的堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 n 的堆上取的纸牌，只能移到编号为n-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 n=4，4堆纸牌数分别为

0
轩爸发布于 2020-05-09 10:20

2推荐

1378浏览

信息学奥赛一本通T1319：贪心算法排队接水

【题目描述】有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。【输入】共两行，第一行为n(1≤n≤1000)；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。【输出】有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)

0
轩爸发布于 2020-05-09 10:20

0推荐

1639浏览

信息学奥赛一本通T1233：贪心算法接水问题

【题目描述】学校里有一个水房，水房里一共装有m个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。现在有n名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n编号，i号同学的接水量为wi。接水开始时，1到m号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j完成其接水量要求wj后，下一名排队等候接水的同学k马上接替j同学的位置开始接水。这个换人的过程是瞬间完成的

0
轩爸发布于 2020-04-30 10:20

0推荐

1418浏览

信息学奥赛一本通T1232：贪心算法 Crossing River

【题目描述】几个人过河，每次过两人一人回，速度由慢者决定，问过河所需最短时间。【输入】输入t组数据，每组数据第1行输入n，第2行输入n个数，表示每个人过河的时间。【输出】输出t行数据，每行1个数，表示每组过河最少时间。【输入样例】1【输出样例】17【源程序】

0
轩爸发布于 2020-04-30 10:20

0推荐

1150浏览

信息学奥赛一本通T1231：贪心算法最小新整数

【题目描述】给定一个十进制正整数n(0<n<1000000000)，每个数位上数字均不为0。n的位数为m。现在从m位中删除k位(0<k<m)，求生成的新整数最小为多少？例如: n=9128456,k=2,则生成的新整数最小为12456。【输入】第一行t, 表示有t组数据；接下来t行，每一行表示一组测试数据，每组测试数据包含两个数字n,k。【输出】t行，每行一个数字，表示从n

0
轩爸发布于 2020-04-30 10:20

0推荐

799浏览

信息学奥赛一本通T1230：贪心算法寻找平面上的极大点

【题目描述】在一个平面上，如果有两个点(x,y),(a,b),如果说(x,y)支配了(a,b)，这是指x≥a,y≥b;用图形来看就是(a,b)坐落在以(x,y)为右上角的一个无限的区域内。给定n个点的集合，一定存在若干个点，它们不会被集合中的任何一点所支配，这些点叫做极大值点。编程找出所有的极大点，按照x坐标由小到大，输出极大点的坐标。本题规定：n不超过100，并且不考虑点的坐标为负数的情况。【输

0
轩爸发布于 2020-04-29 16:20

1推荐

727浏览

信息学奥赛一本通T1229：贪心算法电池的寿命

【题目描述】小S新买了一个掌上游戏机，这个游戏机由两节5号电池供电。为了保证能够长时间玩游戏，他买了很多5号电池，这些电池的生产商不同，质量也有差异，因而使用寿命也有所不同，有的能使用5个小时，有的可能就只能使用3个小时。显然如果他只有两个电池一个能用5小时一个能用3小时，那么他只能玩3个小时的游戏，有一个电池剩下的电量无法使用，但是如果他有更多的电池，就可以更加充分地利用它们，比如他有三个电池分

0
轩爸发布于 2020-04-29 16:20

0推荐

1005浏览

信息学奥赛一本通T1228：贪心算法书架

【题目描述】John最近买了一个书架用来存放奶牛养殖书籍，但书架很快被存满了，只剩最顶层有空余。John共有N头奶牛(1≤N≤20,000)，每头奶牛有自己的高度Hi(1≤Hi≤10,000)，N头奶牛的总高度为S。书架高度为B(1≤B≤S<2,000,000,007)。为了到达书架顶层，奶牛可以踩着其他奶牛的背，像叠罗汉一样，直到他们的总高度不低于书架高度。当然若奶牛越多则危险性越大。为了

0
轩爸发布于 2020-04-29 16:20

0推荐

988浏览

信息学奥赛一本通T1226：贪心算法装箱问题

【题目描述】一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个型号，他们的长宽分别为1*1,2*2,3*3,4*4,5*5,6*6。这些产品通常使用一个6*6*h的长方体包裹包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。【输入】输入文件包括几行，每一行代表

0
轩爸发布于 2020-04-29 16:20

0推荐

733浏览

信息学奥赛一本通T1227：贪心算法 Ride to Office

【题目描述】起点与终点相隔4500米。现Charley 需要从起点骑车到终点。但是，他有个习惯，沿途需要有人陪伴，即以相同的速度，与另外一个人一起骑。而当他遇到以更快的速度骑车的人时，他会以相应的速度跟上这个更快的人。先给定所有与Charley 同路的人各自的速度与出发时间，问Charley 以这种方式跟人，骑完4500米需要多少时间。得出的结果若是小数，则向上取整。【输入】输入若干组数据，每组

0
轩爸发布于 2020-04-29 16:20

0推荐

1103浏览

信息学奥赛一本通T1225：贪心算法金银岛

【题目描述】某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为w的物品。岛上金属有s个种类, 每种金属重量不同，分别为n1,n2,...,ns，同时每个种类的金属总的价值也不同，分别为v1,v2,...,vs。KID想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意到金

0
轩爸发布于 2020-04-29 10:20

0推荐

1071浏览

信息学奥赛一本通T1224：贪心算法最大子矩阵

【题目描述】已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1×11×1)子矩阵。比如，如下4×4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1-1 8 0 -2的最大子矩阵是 9 2-4 1-1 8这个子矩阵的大小是15。【输入】输入是一个N×N的矩阵。输入的第一行给出

0
轩爸发布于 2020-04-29 10:20

0推荐

1162浏览

信息学奥赛一本通T1223：贪心算法 An Easy Problem

【题目描述】给定一个正整数N，求最小的、比N大的正整数M，使得M与N的二进制表示中有相同数目的1。举个例子，假如给定的N为78，其二进制表示为1001110，包含4个1，那么最小的比N大的并且二进制表示中只包含4个1的数是83，其二进制是1010011，因此83就是答案。【输入】输入若干行，每行一个数n(1≤n≤1000000)，输入"0"结束。【输出】输出若干行对应的值。【输入样例】1【输出样例

0
轩爸发布于 2020-04-29 10:20