i3geek.com
闫庚哲的个人博客

1016 货币面值【网易游戏2013年校园招聘笔试题】

进入OJ

Description

小虎是游戏中的一个国王,在他管理的国家中发行了很多不同面额的纸币,用这些纸币进行任意的组合可以在游戏中购买各种装备来提升自己。有一天,他突然很想知道这些纸币的组合不能表示的最小面额是多少,请聪明的你来帮助小虎来解决这个财政问题吧。

Input

输入包含多个测试用例,每组测试用例的第一行输入一个整数N(N<=100)表示流通的纸币面额数量,第二行是N个纸币的具体表示面额,取值[1,100]。

Output

对于每组测试用例,输出一个整数,表示已经发行的所有纸币都不能表示的最小面额(已经发行的每个纸币面额最多只能使用一次,但面值可能有重复)。

Sample Input

5
1 2 3 9 100
5
1 2 4 9 100
5
1 2 4 7 100

Sample Output

7
8
15

Hint

动态规划

Source

网易游戏2013年校园招聘笔试题

Code

//动态规划的思想, 对于从第1个到第i个数的和total,  
//如果第i+1个数大于total+1则不会组成total+1.
#include<stdio.h>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    int a[110];
    while(scanf("%d",&n)!=EOF)
    {
        for(int i =0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a + n);
        int sum=0;
        for(int i=0;i<n;i++)
        {

            if(sum+1<a[i])
                break;

            sum = sum+a[i];
        }
        printf("%d\n",sum+1);
    }
}

 

赞(0)
未经允许不得转载:爱上极客 » 1016 货币面值【网易游戏2013年校园招聘笔试题】
分享到: 更多 (0)

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    当年很想进微软的,但是现在没有这个动力了

    知道91博客5年前 (2014-12-04)回复