# Discount

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 984    Accepted Submission(s): 591

Problem Description

All the shops use discount to attract customers, but some shops doesn’t give direct discount on their goods, instead, they give discount only when you bought more than a certain amount of goods. Assume a shop offers a 20% off if your bill is more than 100 yuan, and with more than 500 yuan, you can get a 40% off. After you have chosen a good of 400 yuan, the best suggestion for you is to take something else to reach 500 yuan and get the 40% off. For the customers’ convenience, the shops often offer some low-price and useful items just for reaching such a condition. But there are still many customers complain that they can’t reach exactly the budget they want. So, the manager wants to know, with the items they offer, what is the minimum budget that cannot be reached. In addition, although the items are very useful, no one wants to buy the same thing twice.

Input

The input consists several testcases. The first line contains one integer N (1 <= N <= 1000), the number of items available. The second line contains N integers Pi (0 <= Pi <= 10000), represent the ith item’s price.

Output

Print one integer, the minimum budget that cannot be reached.

Sample Input

4 1 2 3 4

Sample Output

11

Source

2011 Alibaba-Cup Campus Contest

Recommend

lcy

这道题，开始以为是母函数，后来觉得数据处理貌似不行。又改为背包，内存直接爆掉了！！，我勒个去，没得办法，之后去了一趟度娘那，

才发现是一道.....貌似不能归于哪一类，就是杂谈吧！

方法是这样的...先进行排序（由小到大）也就是升序....然后用他后面n-1一项的和加1来与当前这项比较，如果当前这项小于前者之和加1,那么就是这个数

，是不能被组合出来的...

就拿 1 2 3 4 这组数据来讲吧.... 开始 sum=0; sum+1<1 ，不满足，所以跳到下一个数，此时sum=1; sum+1<2.。又不满足，所以继续...依次-----最后..还是不满足。

所以就输出 sum+1( 注意此时的sum=1+2+3+4=10)，所以 输出的是10.

再比如 1 3 4 5  begin sum=0; sum+1<1 不满足，继续...sum+=1；sum+1<3；满足，所以终止，输出；

依据这一原理：

代码如下：

``` 1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #define maxn 1001
5 using namespace std;
6 int value[maxn];
7 int main()
8 {
9     int n,i,sum;
10     while(~scanf("%d",&n))
11     {
12         for(i=0;i<n;i++)
13             scanf("%d",value+i);
14         sort(value,value+n);
15         sum=0;
16         for(i=0;i<n;i++)
17        {
18             if(sum+1<value[i])
19                 break;
20             sum+=value[i];
21        }
22         cout<<sum+1<<endl;
23     }
24  return 0;
25 }```

0 条评论

• ### hdu----(5050)Divided Land(二进制求最大公约数)

Divided Land Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536...

• ### HDUOJ-Counting Triangles

Counting Triangles Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536...

• ### HDUOJ----1003 Max Sum

Max Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (J...

• ### 浙大版《C语言程序设计（第3版）》题目集 习题2-3 求平方与倒数序列的部分和

本题要求对两个正整数m和n（m≤n）编写程序，计算序列和m2+1/m+(m+1)​2+1/(m+1)+⋯+n2+1/n。

• ### DAY89：阅读Unified Memory Programming

我们正带领大家开始阅读英文的《CUDA C Programming Guide》,今天是第89天，我们正在讲解Unified Memory Programmin...

• ### 01计算机基本组成

CPU的种类 cpu的内部集成了一些指令集，所有软件的运行都需要cpu中的这些指令集来完成。根据指令集的不同，cpu被分为两类：含有精简指令集的cpu和含有复杂...

• ### 如何使用UI Configuration将WebClient UI的隐藏字段放出来

In Service order detail page some fields are by default hidden in standard UI co...

• ### Fortran知识 | 代码错误（数组越界）

如图所示，提示为： Subscript #1 of the array INDEX has value 61 which is greater than the...