动态规划进阶题目之货币面值

时间: 1ms        内存:64M

描述:

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

输入:

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

输出:

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

示例输入:

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

示例输出:

7
8
15

提示:

参考答案(内存最优[1092]):

#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
int main()
{
    int a[110];
    int n,i;
    while(~scanf("%d",&n))
    {
        int i;
        int sum=0;
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        qsort(a,n,sizeof(a[0]),cmp);
        for(i=0;i<n;i++)
        {
            if(sum+1<a[i])
                break;
             sum+=a[i];
        }
        printf("%d\n",sum+1);
    }
    return 0;
}

参考答案(时间最优[0]):

#include <stdio.h>
#include <stdlib.h>
/*先排序。然后从小到大相加。比如在 i 处。只要0到i-1的所有值之和都小于i-1。那么可以说所构成的值到此为止出现“断面”。即无法连续。输出前面0到i-1的值之和再加一就好了。*/
int Compare(const void * p, const void * q){
    return *(int *)p - *(int *)q;
}

int main(){
    int N;
    int value[100];
    int i;
    int ans;

    while (scanf("%d", &N) != EOF){
        for (i = 0; i < N; ++i){
            scanf("%d", &value[i]);
        }
        qsort(value, N, sizeof(int), Compare);
        ans = 0;
        for (i = 0; i < N; ++i){
            if (value[i] > ans + 1){
                break;
            }
            else
                ans += value[i];
        }
        printf("%d\n", ans + 1);
    }

    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。