首页 > ACM题库 > 九度OJ > 九度-1531-货币面值[解题代码]
2013
12-13

九度-1531-货币面值[解题代码]

题目来源:网易游戏2013年校园招聘笔试题

题目描述:

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

输入:

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

输出:

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

样例输入:
5
1 2 3 9 100
5
1 2 4 9 100
5
1 2 4 7 100
样例输出:
7
8
15

cpp 代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    int a[110],n;
    while(scanf("%d",&n) != EOF) {
        for(int i = 1; i <= n; i ++)
            scanf("%d",&a[i]);
        a[0] = 0;
        sort(a + 1,a + n + 1);
        int ans = 0;
        for(int i = 1; i <= n; i ++)
            if(a[i] > ans + 1) {
                break;
            }
            else ans += a[i];
        printf("%d\n",ans + 1);
    }
    return 0;
}

/**************************************************************
	Problem: 1531
	User: coder
	Language: C++
	Result: Accepted
	Time:10 ms
	Memory:1520 kb
****************************************************************/


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.