菜鸟求助题目:蜡烛
pascal吧
全部回复
仅看楼主
level 11
突破天界 楼主
【问题描述】
奶牛bessie有n根蜡烛,第i根蜡烛的长度是h[i]. bessie最近刚上完小学,只会加减法。它想知道它的n根蜡烛最多能用多少个晚上。由于bessie比较胆小,因此它第一个晚上只点燃一根蜡烛,第二个晚上点燃两根蜡烛,第三个晚上点燃三根蜡烛…第i个晚上它必须要点燃i根蜡烛。每根被点燃的蜡烛,它燃烧一个晚上会使得它的长度减少1。一旦蜡烛的长度变成0,那么该根蜡烛就用完了。如果第i个晚上bessie发现不够i根蜡烛用了,那么bessie最多就只能用i-1个晚上. Bessie想知道,它该如何选择每个晚上点燃哪些蜡烛,使得它的n根蜡烛能用尽量多的晚上。输出最多能用多少个晚上。
【输入格式】
第一行:一个整数n, 1 <= n <= 50. 第二行:n个整数,第i个整数表示第i根蜡烛的长度h[i]. 1 <= h[i] <= 100.
【输出格式】
一个整数,总共最多能用多少个晚上.
【输入样例】
3
2 2 2
【输出样例】
3
谢谢各位吧友了!
2014年04月21日 04点04分 1
level 11
这题可以用贪心,很明显蜡烛会越用越快,所以可以先将数据排好序,第i天就把最长的i根蜡烛长度减少1,并调整数组使他变得有序(用到长度为0时就将蜡烛个数减少1),如果发现不够i根蜡烛,就退出循环输出答案。又因为n<=50,h[i]<=100所以这个复杂度是完全可以接受的
2014年04月22日 05点04分 2
1