2 shunfurh shunfurh 于 2017.09.17 22:21 提问

Beans

Problem Description
Mr. Pote's shop sells beans now. He has N bags of beans in his warehouse, and he has numbered them with 1, 2, …, N according to their expired dates. The i-th bag contains Wi units of beans. For selling at retail makes only a little profit, Mr. Pote want to pack beans in small packets with certain size and sell them in packets. Here comes his packing way:
Suppose the size of the packet is P units. Firstly, Mr. Pote selects some bags (at least one) of beans with consecutive number in his warehouse. Then he takes out the beans from all selected bags, and puts them together on the desktop. To pack the beans, he take P units of beans from desktop and fill in a new packet each time, until the beans left are less than P units. Finally the beans left on the desktop are eaten by a lucky dog.
Mr. Pote doesn't want the dog eat too many beans, so he prefers to solutions that resulting no more than K units of beans eaten by the dog. Moreover, he also wants to pack as many packets as possible. Could you tell him how many packets he can pack at most without breaking his preference?

Input
On the first line of input, there is a single positive integer T <= 20 specifying the number of test cases to follow.
Each test case contains two lines.
There are three integers in the first line, N, P, K as described above. (0 < N, P < 1000001, 0 <= K < P)
Next follow a line with N integers W1, W2, ..., WN. The i-th integers describes the amount of beans in the bags numbered i. (0 <= Wi < 32768)
Numbers are separated by spaces.

Output
For each test case you should output a single line containing "Case X: Y" (quotes for clarity) where X is the number of the test case (starting at 1) and Y is the maximum number of packets that Mr. Pote can pack following his way.
In case there's no solution avoiding the dog eats more than K units of beans, Y should be equal to -1.

Sample Input
3
10 20 10
0 3 1 8 19 39 2 9 1 8
3 100 10
32 34 23
1 5 3
1

Sample Output
Case 1: 4
Case 2: -1
Case 3: 0

1个回答

caozhy
caozhy   Ds   Rxr 2017.10.02 08:51
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Beans使用 Beans使用
Beans使用 Beans使用 Beans使用
Spring:IoC 用法(七、<beans>用法)
元素属性详细讲解 id 别名 class scope value ref c:命名空间 p:命名空间 util:命名空间 对应 @Bean操作
Spring中beans标签定义
tag --> <![CDATA[ Container for and other elements, typically the root element in the document. Allows the definition of default values for all nested bean definitions. May itself be neste
Spring配置文件中的<beans>标签
beans 标签中的一大串网址还是比较令人在意的,所以整理以下 beans 标签中各个属性的意思,方便理解。
Spring Beans实例化
如果说Spring最核心的东西是什么,那就非Beans组件莫属了,Bean对于Spring的意义就象OOP对于Java的意义一样。本文基于Spring Boot1.4x来分析下Spring是如何实例化Bean。我们将会从Bean的定义、创建以及解析几个方面来分析。 首先来说说Spring是如何找到并解析Bean属性的。如果使用注解的方式则Spring在启动初始化的时候会扫描项目classpath
Spring学习笔记(十七):spring配置文件详解以及beans:beans标签
<beans:beans xmlns="http://www.springframework.org/schema/security" xmlns:beans="http://www.springframework.org/schema/beans" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLoca
IntelliJ Idea解决Could not autowire. No beans of 'xxxx' type found的错误提示
1.问题描述   在Idea的spring工程里,经常会遇到Could not autowire. No beans of 'xxxx' type found的错误提示。但程序的编译和运行都是没有问题的,这个错误提示并不会产生影响。但红色的错误提示在有些有强迫症的程序员眼里,多多少少有些不太舒服。   2. 原因   spring auto scan配置,在编辑情况下,无法找不到对应的
SSH整合报错:找不到元素 'beans' 的声明
spring版本问题,将bean.xml中xsd文件定义的版本改为spring jar包中定义的xsd的版本。注意标注版本的时候,写两位(3.2.)就好了,不要写三位(3.2.5),会报错的。 xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"  xmlns:p="http://www.springframework.org/sche
Spring boot 嵌入的tomcat不能启动: Unregistering JMX-exposed beans on shutdown
在官网(http://start.spring.io/)上generate project,将生成的项目导入idea中,运行之后控制台输出“Unregistering JMX-exposed beans on shutdown”,tomcat也没有运行。
Spring3自定义环境配置 <beans profile="">
转:http://nassir.iteye.com/blog/1535799/ 摘自springside3  Spring 3.1的功能,以后就不用为了区分Test, Dev, Production环境,搞几个只有细微区别的application.xml, application-test.xml及引用它们的web.xml了。 首先,将applicationContext.x