当前位置:   article > 正文

zzulioj新生周赛(6) 2733 问题K : 键盘霸主hrs_oj新生周赛有多少题

oj新生周赛有多少题

题目描述

众所周知,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

样例输入

3
3
1 2 3
3
3 3 3
3
1 1 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

思路

利用散列,先将其范围变成一个数组x[10005],初始化为0;每输入一个值a从后往前遍历一遍数组;如果发现哪个的值不为0;将其下标加上a,并将新得到的下标对应的数组元素自加,遍历完后,下标为a的数组元素自加;输入完成后,再从前往后遍历找到元素值位0的下标,自减后输出。

注:从后往前遍历,如果从前往后,因为如果发现b的值不为0;将其下标加上a,然后x[b+a],x[b+a+a],x[b+a+a+a]......就都自加了;

  1. #include<stdio.h>
  2. #include<string.h>
  3. int main()
  4. {
  5. int y[10006];
  6. int a,b,c,d,e,f;
  7. scanf("%d",&a);
  8. while(a--)
  9. {
  10. memset(y,0,sizeof(y));
  11. scanf("%d",&b);
  12. for(c=0;c<b;c++)
  13. {
  14. scanf("%d",&e);
  15. for(d=10000;d>=1;d--)
  16. {
  17. if(y[d]!=0)
  18. y[d+e]++;
  19. }
  20. y[e]++;
  21. }
  22. for(c=1;c<=10000;c++)
  23. if(y[c]==0)
  24. {
  25. printf("%d\n",c-1);
  26. break;
  27. }
  28. }
  29. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/884233
推荐阅读
相关标签
  

闽ICP备14008679号