赞
踩
众所周知,hrs学长实力强悍,就没有我hrs不会的题。打比赛的时候经常占着键盘不下来。
队友第一次来借键盘:hrs:“等会儿,这道题我快A了”。
几分钟过后,队友第二次来借键盘:hrs:“慌啥,刚刚题意弄错了,我改下”。
十分钟过后,队友又来催了,hrs:“你在教我做事”
。。。。。。
几分钟后,hrs学长极不情愿地离开他心爱的键盘。
队友成功地摸到了键盘,看着手下熟悉而又陌生的键盘,队友一时间竟不知道该做些什么。就在这时,hrs的声音响起。“给你10分钟写这题,写不完就换我来”,hrs学长太强了,队友苦思冥想两个小时的题,对hrs来说,不过是一眼题罢了。
什么,你说前面有道题说hrs很菜,一眼看不出来。→_→,那道题是他自己出的,那叫谦虚,懂?
啥,你还觉得hrs学长是个cj。
这样,来看看hrs学长的一眼题。
这里有n个小球,每个小球都有一个随机编号。你可以执行以下操作。
从这n个小球挑选出几个小球,将这些小球上面的编号相加,这样我们就得到了一个数字。
令mi为无法通过以上操作得到的最小正整数,输出mi-1。
第一行一个数字T,表示T组测试数据。(0<T≤10)
每组数据有两行输入。
第一行一个整数n,表示小球的个数。(1≤n≤ 10)
第二行n个整数a1,a2,a3,…,an(1≤i≤n,0<ai≤1000),表示小球上面的编号。
输出每组数据的mi-1
6
0
3
样例解释:
[1 2 3]
1:1
2:2
3:3
4:1+3
5:2+3
6:1+2+3
7:无法得到。mi=7
输出mi-1=6
[3 3 3]
1:无法得到。mi=1
输出mi -1=0
[1 1 1]
1:1
2:1+1
3:1+1+1
4:无法得到,mi=4
输出mi-1=3
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,a[15],b[100005]={0};b[0]=1;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<n;i++)
{
for(int j=10000;j>=0;j--) //注意这里不可以从0开始到10000结束
{
if(b[j]==1)
{
b[j+a[i]]=1;
}
}
}
for(int i=0;i<10000;i++)
{
if(b[i]==0)
{
printf("%d\n",i-1);
break;
}
}
}
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。