货币面值
时间限制:1 秒
内存限制:128 兆
特殊判题:否
提交:351
解决:132
题目描述:
小虎是游戏中的一个国王,在他管理的国家中发行了很多不同面额的纸币,用这些纸币进行任意的组合可以在游戏中购买各种装备来提升自己。有一天,他突然很想知道这些纸币的组合不能表示的最小面额是多少,请聪明的你来帮助小虎来解决这个财政问题吧。
输入:
输入包含多个测试用例,每组测试用例的第一行输入一个整数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
先排序。然后从下到大相加。比如在 i 出。只要0到i-1的所有值之和都小于i-1。那么可以说所构成的值到此为止出现“断面”。即无法连续。输出前面0到i-1的值之和再加一就好了。
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n,val[110];
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>val[i];
}
sort(val,val+n);
int sum=0;
for(int i=0;i<n;i++)
{
if(sum+1<val[i])
break;
sum+=val[i];
}
cout<<sum+1<<endl;
}
}
/*第一次的时候for循环我是这么写的
*/
for(int i=0;i<n-1;i++)
{
sum+=val[i];
if(sum+1<val[i+1])
break;
}
/*这个有严重问题。
举例:n=5时
1、2、3、5、6
这样在sum=1+2+3+5=11的时候就结束循环了。输出12(sum+1)
而如果将循环改为:*/
for(int i=0;i<n;i++)
{
sum+=val[i];
if(sum+1<val[i+1])
break;
}
/*这时在遍历到i=n-1:
即sum=11+6=17的时候
会试探着比较sum+1和val[i+1]也就是val[7]
而val[7]的值是不确定的。
*/
分享到:
相关推荐
京东 校园招聘笔试试题--软件开发笔试题 -.docx京东 校园招聘笔试试题--软件开发笔试题 -.docx京东 校园招聘笔试试题--软件开发笔试题 -.docx京东 校园招聘笔试试题--软件开发笔试题 -.docx京东 校园招聘笔试试题--...
奥克斯集团2013年校园招聘笔试题-硬件类试题
奥克斯集团2013年校园招聘笔试题-制冷(系统)类试题
百度 2014校园招聘笔试试题--深度学习算法研发工程师.docx百度 2014校园招聘笔试试题--深度学习算法研发工程师.docx百度 2014校园招聘笔试试题--深度学习算法研发工程师.docx百度 2014校园招聘笔试试题--深度学习...
奥克斯集团2013年校园招聘笔试题-管理类试题
奥克斯集团2013年校园招聘笔试题-软件类试题
百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园...
奥克斯 2013年校园 招聘 笔试题 财务类 试题
基恩士2013校园招聘笔试题-销售
携程历年校园招聘笔试试题 -.docx携程历年校园招聘笔试试题 -.docx携程历年校园招聘笔试试题 -.docx携程历年校园招聘笔试试题 -.docx携程历年校园招聘笔试试题 -.docx携程历年校园招聘笔试试题 -.docx携程历年校园...
百度2010-2011年各部门招聘笔试题及面经总结.doc 百度2014校园招聘笔试试题-产品经理笔试题.doc 百度2014校园招聘笔试试题-北京站未知岗位.docx 百度2014校园招聘笔试试题-南京PC客户端开发笔试题.doc 百度2014校园...
百度2014校园招聘笔试试题-研发工程师笔试题.docx
奇虎360 2013校园招聘笔试试题-技术类-高清无答案.docx
奇虎360 2013校园招聘笔试试题-产品类-华中科技大学.doc
奇虎360 2013校园招聘笔试试题-产品类-华中科技大学.pdf
2013年阿里巴巴校园招聘笔试试题研发工程师.doc 2014年3月阿里巴巴实习招聘笔试题及部分答案.docx 2014年阿里巴巴校园招聘笔试题杭州站-研发类.doc 淘宝2011实习招聘笔试.doc 淘宝校园招聘清华笔试试题.doc 淘宝校园...
2013去哪儿网校园招聘笔试试题--技术类.docx