2307. Pirates’ Gold

单点时限: 2.0 sec

内存限制: 256 MB

You have stolen the pirates’ gold! You have a number of pieces of gold worth various amounts of money. You can think of your loot as a set of positive integers (with possible duplicates). For example, the set {7, 10, 13, 4, 10, 24} means that you have:

(Note that the order in which the amounts are listed does not matter.)

The pirates catch up to you and demand that you give it back or you will have to “walk the plank.” Luckily for you, pirates are not very good at math, and they do not know exactly how much you stole. They boldly say, “We claim that you stole at least $xxx dollars worth of gold!” Since you want to live, you need to give back at least as much as they claim. However, since you are greedy you want to give back as little additional as possible.

Write a program that will save your life, but save as much loot for you as possible. Given a list of the values of the gold that you stole and given how much the pirates claim you stole (both in dollars) determine the minimal amount that you need to give back so that you give back at least as much as you stole. If the total amount that the pirates claim exceeds the total that you stole, then you’re dead! In this case your program should return the special value -1.

For example, suppose you have the stolen amounts {7, 10, 13, 4, 10, 24} and the pirates claim that you stole at least 25.

输入格式

We have provided a main program for you that handles all the input and output. (The first number is the pirates’ claim followed by the amounts you stole.) The list of stolen amounts is stored in an array stolen[ ]. (All amounts are positive. You may obtain the number of values as stolen.length.) The pirates’ claim of the amount you stole is given by the variable claim. (The claim a nonnegative integer.)

输出格式

You are to write the function payBack(), which will return the minimum amount you should pay back, or else return -1 if it is impossible to satisfy the pirates’ claim.

private static int payBack(int stolen[], int claim);

Here are some samples. In the first case payBack() returns 27 and in the other it returns -1.

样例

Input
25 7 10 13 4 10 24
/*
100 7 10 13 4 10 24
*/
Output
Values of stolen items: 7 10 13 4 10 24
Pirates' claim = 25
Final pay back = 27
/*
Values of stolen items: 7 10 13 4 10 24
Pirates' claim = 100
I'm dead!
*/

10 人解决,24 人已尝试。

11 份提交通过,共有 60 份提交。

7.2 EMB 奖励。

创建: 11 年,5 月前.

修改: 2 年,5 月前.

最后提交: 11 月,4 周前.

来源: 2007 Maryland High-school Programming Contest

题目标签
DP