首页 > 试题广场 >

数字游戏

[编程题]数字游戏
  • 热度指数：21290 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
小易邀请你玩一个数字游戏，小易给你一系列的整数。你们俩使用这些整数玩游戏。每次小易会任意说一个数字出来，然后你需要从这一系列数字中选取一部分出来让它们的和等于小易所说的数字。 例如： 如果{2,1,2,7}是你有的一系列数，小易说的数字是11.你可以得到方案2+2+7 = 11.如果顽皮的小易想坑你，他说的数字是6，那么你没有办法拼凑出和为6 现在小易给你n个数，让你找出无法从n个数中选取部分求和的数字中的最小数（从1开始）。

输入描述:
输入第一行为数字个数n (n ≤ 20)
第二行为n个数xi (1 ≤ xi ≤ 100000)


输出描述:
输出最小不能由n个数选取求和组成的数
示例1

输入

3
5 1 2

输出

4
算法知识视频讲解
添加回答
C/C++
骏博日博的迷弟头像 骏博日博的迷弟
基于这样一种迭代的思想：我当前假如说可以得到最大的数为k，则再来一个新的数字p，若p<=k+1，则我可以得到的最大的数为p+k，若p>k+1，则会出现空挡，k+1就肯定不能再得到。 
#include <cstdio>
#include <algorithm>

int main()
{
    int x[25], n;
    while(scanf("%d", &n)!=EOF)
    {
        for(int i=0 ;i<n; i++)
            scanf("%d", x+i);
        std::sort(x,x+n);
        int ans = 0;
        for(int i=0; i<n; i++)
        {
            if(x[i]>(ans+1))
                break;
            ans+=x[i];
        }
        printf("%d\n", ans+1);
    }
    return 0;
}

发表于 2017-08-08 13:56:40 回复(8)
牛客470556号头像 牛客470556号 
/*
* Sort后，查看有序数组的前 n 项和是否与当前项连续，
* 如果不连续说明存在一个空档无法通过求和得到
* */

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    private static int check(int[] X, int n){
        if (X[0]>1) return 1;
        else if (n == 1) return X[0]+1;
        else {
            int sum = X[0];
            for (int i = 1; i < n; i++) {
                if (X[i]-sum>1) break;
                else sum += X[i];
            }
            return sum+1;
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] X = new int[n];
            for (int i = 0; i < n; i++) {
                X[i] = in.nextInt();
            }
            Arrays.sort(X);
            System.out.println(check(X, n));
        }
    }
}

发表于 2016-08-07 12:07:02 回复(12)
smallx头像 smallx 
import java.util.*;

/**
 * 背包问题的一种，本质为"若num小于不可解的最小数，那么1,2,3...num都是可解的"。
 *
 * 思路如下：
 *
 * 将给定的数据集nums从大到小排序。我们要判断命题"num小于不可解的最小数"是否成立。
 * 我们将num看作背包，然后从nums中拿出一个最大的值v，如果num中能够放得下就放进去，
 * 如果放进去后刚好满了，则num可解，命题成立，如果不满继续迭代；如果v放不进去背包中了，
 * 那么背包剩下的容量构成一个更小的子问题(<num)，并且如果想要命题成立，那么该子问题
 * 必定可解，并且解必定由v后边的数字序列构成(已从大到小排序)。
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int[] nums = new int[n];
            for(int i=0; i<n; i++)
                nums[i] = scanner.nextInt();

            Arrays.sort(nums);
            long num = 1;
            while (true) {
                long sum = 0;
                for(int i=n-1; i>=0 && sum!=num; i--) {
                    if(nums[i] + sum <= num)
                        sum += nums[i];
                }
                if (sum != num) {
                    System.out.println(num);
                    break;
                }
                num++;
            }
        }
    }
}
编辑于 2016-08-07 20:01:47 回复(6)
人民的名义头像 人民的名义

Python:如果第【i】个大于当前sum和+1说明，前i个数字和无法组成当前sum和+1

 
    该值即所求当前最小值， 
def Min_Sum(ls,n):
    #对输入内容进行有效性判断
    if n>20 or [i  for i in ls if i not in range(1,100001)]:
        return 0
    #排序
    ls.sort()
    #初始的和为0
    sumOfPre=0
    for i in range(0,n):
        #如果前几个数的和加一小于当前值 ，则说明 有空的间隔的值，停止循环，否则继续进行和计算
        if (sumOfPre+1)<ls[i]:
            break
        else:
            sumOfPre+=ls[i]
    return (sumOfPre + 1)
if __name__=="__main__":
    n = int(input())
    ls =[int(i) for i in input().split()]
    count=Min_Sum(ls,n)
    print(count)
发表于 2017-10-16 18:34:17 回复(1)
小伟成头像 小伟成

根据第一个回答,整理一下
假设排序后前 x 个数可以组成 [1,sum(a[x])]
之中的任意一个数
若 第 x+1 个数 a[x]> sum(a[x])+1
那么前 x+1 个数只能组成 [1,sum(a[x])],[a[x+1],sum(a[x])]
中间会出现一个范围为 [sum(a[x])+1,a[x]-1] 的断层

发表于 2017-09-07 16:47:31 回复(1)
Python
Prominent头像 Prominent
n = int(input().strip())
seq = list(map(int,input().strip().split()))
seq.sort()
max_num = 0
for num in seq[:]:
    if num <= max_num+1:
        max_num = max_num + num
    else:
        print(max_num+1)
        break
else:
    print(max_num+1)
发表于 2018-09-05 19:41:11 回复(0)
丨Morpheus头像 丨Morpheus 
n = int(raw_input())
res=map(int,raw_input().strip().split())
res.sort()
for i in range(len(res)-1):
    if res[i+1]>sum(res[:i+1])+1:
        print sum(res[:i+1])+1
        break
    if res[0]>1:
        print 1
        break
else:
    print sum(res)+1

发表于 2018-08-20 15:54:46 回复(0)
啊咿呀嘿头像 啊咿呀嘿

一楼大佬确实流弊，小弟在此借鉴一下

<?php

$n = trim(fgets(STDIN));

$num = explode(" ", trim(fgets(STDIN)));

sort($num);

$miss = 0;//让miss初始为0

for($i=0; $i<$n; $i++){
        if($num[$i]>$miss+1){
                break;
        }
        $miss += $num[$i];//累加
}

echo $miss+1;
发表于 2017-09-14 09:40:49 回复(0)
rs勿忘初心头像 rs勿忘初心 
//将数组vec所有元素排序，比如：1,2,5，6...
//前i-1个元素的和sum，初始值设为0，每次判断sum+1与第i个元素的大小关系
//（sum+1与vec[i]）,若sum+1<vec[i],说明sum与vec[i]之间出现了断裂，sum+1
//即为最小的断裂元素（不可能由前面的元素组合成）。
//比如当i=2时，sum=vec[0]+vec[1]=1+2=3,则0~3是可以连续取到的，而此时sum+1<5，
//即3~5之间出现了断裂，4是取不到的。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
  {
      int n;
      while(cin>>n)
        {
            vector<int> vec;
            for(int i=0;i<n;i++)
              {
                  int number;
                  cin>>number;
                  vec.push_back(number);
              }
            sort(vec.begin(),vec.end());
            long long sum=0;
            int i;
            for(i=0;i<n;i++)
              {
                  if(sum+1<vec[i])
                      break;
                  sum+=vec[i];
              }
            cout<<sum+1<<endl;
        }
  }

编辑于 2017-09-03 20:23:23 回复(3)
元气の悟空头像 元气の悟空 
#include<stdio.h>
#include<string.h>
int a[25],book[2000005];
int main(){
	int N,i,j;
	//freopen("input.txt","r",stdin);
	while(scanf("%d",&N)!=EOF){
		memset(book,0,sizeof(book));
		for(i=0;i<N;i++) scanf("%d",&a[i]);
		for(i=0;i<1<<N;i++){
			int res=0;
			for(j=0;j<N;j++)
				if(i>>j&1) res+=a[j];
			book[res]=1;
		}
		for(i=1;i<=2000000;i++)
			if(book[i]==0) break;
		printf("%d\n",i);
	}
}//这么小的数据，直接枚举所有子集就可以啦~

发表于 2017-08-30 16:07:20 回复(0)
龙虾姐夫头像 龙虾姐夫 
题目有个重要规律：先把n个数从小到大排序后，得到数组array.分别计算前i项的和Sum(i),    若Sum(i)<array[i+1]-1,则必然存会一个题目所求的数M，Sum(i)<M<array[i+1]
                                                 最小的M=Sum(i)+1; 


	importjava.util.*;





	publicclassMain{





	     





	    publicstaticvoidmain(String[] args)





	    {





	        Scanner scan =newScanner(System.in);





	         





	        while(scan.hasNext())





	        {





	            intn=scan.nextInt();





	             





	            int[] numArr=newint[n];





	             





	            for(inti=0;i<n;i++)





	            {





	                numArr[i]=scan.nextInt();





	            }





	             





	            Arrays.sort(numArr);





	             





	            intmin=getMinAdd(numArr);





	            System.out.println(min);





	             





	        }





	    }





	     





	    publicstaticintgetMinAdd(int[] numArr)





	    {





	        inti=0;





	        if(numArr[0]!=1)





	        {





	            return1;





	        }





	        while(i<numArr.length-2)





	        {





	            





	           if(sum(numArr,i)<numArr[i+1]-1)





	           {





	               returnsum(numArr,i)+1;





	           }





	            i++;





	 





	        }





	        if(sum(numArr,numArr.length-2)<numArr[numArr.length-1]-1)





	        {





	            returnsum(numArr,numArr.length-2)+1;





	        }





	        else





	        {





	            returnsum(numArr,numArr.length-1)+1;





	        }





	         





	    }





	     





	    publicstaticintsum(int[] numArr,intn)





	    {





	        intsum=0;





	        for(inti=0;i<=n;i++)





	        {





	            sum=sum+numArr[i];





	        }





	        returnsum;





	    }





	     





	   


}

发表于 2016-09-05 17:16:56 回复(0)
牛客677436号头像 牛客677436号 
import java.util.*;
public class Main{
    public static int minNum(int[] num){
        Arrays.sort(num);
        int number=1;
        if(num[0]!=1){
            return 1;
        }
        if(num.length==1){
            return num[0]+1;
        }
        else{
            for(int i=1;i<num.length;i++){
                if(num[i]-number>1){
                    break;
                }
                else{
                    number+=num[i];
                }
            }
        }
        return number+1;
    }
    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        while(s.hasNext()){
            int n=s.nextInt();
            int num[]=new int[n];
            for(int i=0;i<n;i++){
                num[i]=s.nextInt();
            }
            System.out.println(minNum(num));
        }
    }
}

发表于 2016-08-11 21:27:49 回复(1)
pein531头像 pein531
先对数组排序，记前n项和为Sn。然后遍历检查第i个数与Si-1的差距是否不超过1，如果差距比1大，说明不连续，存在空档，Si-1+1肯定凑不出来，这就是凑不出来的最小数。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strArr = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]);
        System.out.println(solve(arr));
    }
    
    private static int solve(int[] arr) {
        Arrays.sort(arr);
        if(arr[0] > 1) return 1;
        if(arr.length == 1) return arr[0] + 1;
        int sum = arr[0];
        for(int i = 1; i < arr.length; i++){
            if(arr[i] > 1 + sum)
                break;
            else
                sum += arr[i];
        }
        return sum + 1;
    }
}

编辑于 2021-04-04 18:25:21 回复(0)
handsome_an头像 handsome_an 
 先排序
 a1 a2  .... an 升序
 首先若a1!=1,那么最小不能组合的数为1
 否则
 sum(1)=a1表示前1个数之和,且sum(1)之内的数都可组合得到
 设sum(i)为前i个数之和,且sum(i)之内的数都可以组合得到
则对于sum(i+1)而言
    若a(i+1)-sum(i)>1,则表示前i个数之和小于a(i+1),也就是说前i个数无法组合成a(i+1)-1,
        也就是说sum(i)和a(i+1)之间必有不能组合的整数,且最小为sum(i)+1;则找到不能组合的最小的数
  若a(i+1)-sum(i)<=1,则sum(i+1)之内的任何数字都可以组合得到因为sum(i)之内的任何数可以得到且ai+1可以得到
 如此递推下去
public static void main(String[] args)throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int x[]=new int[n];
        String[] strs=br.readLine().split(" ");
        for(int i=0;i<n;i++){
            x[i]=Integer.parseInt(strs[i]);
        }
        //排序
        Arrays.sort(x);
        if(x[0]>1){
            System.out.println(1);
            return;
        }
        int sum=0;
        for(int i=0;i<n-1;i++){
            sum+=x[i];
            if(x[i+1]-sum>1){
                System.out.println(sum+1);
                return;
            }
        }
        System.out.println(sum+x[n-1]+1);
    }
发表于 2018-12-14 15:52:36 回复(0)
Python
TimeMac头像 TimeMac 
while True:
    try:
        num,digitList = int(input()),list(map(int,input().split()))
        digitList.sort()
        pieceNum = 0             #表示此前已经可以拼凑前pieceNum的数了
        for i in digitList:
            if pieceNum+1 >= i:   #如果当前i比pieceNum+1还要大，则这些数凑不出pieceNum+1
                pieceNum += i     #此时能凑的最大数为pieceNum+i
            else:
                print(pieceNum+1)
                break
        else:
            print(pieceNum+1)
    except Exception:
        break
编辑于 2018-09-24 00:05:50 回复(0)
Java
黄小斜头像 黄小斜 
import java.util.*;
//先排序，记录可以累加到的和在map中，按顺序遍历，一旦出现空缺元素那就是不能累加到的第一个元素
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        int n = Integer.parseInt(line);
        line = scanner.nextLine();
        String []s = line.split(" ");
        int []arr = new int[n];
        for (int i = 0;i < n;i ++) {
            arr[i] = Integer.parseInt(s[i]);
        }
        System.out.println(min(arr));
    }
    public static int min(int []arr) {
        Arrays.sort(arr);
        if (arr[0] != 1) {
            return 1;
        }
        int max = arr[0];
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
        Set<Integer> set = map.keySet();
        for (int i = 0;i < arr.length;i ++) {
            if (arr[i] - max > 1)return max + 1;
            List<Integer> list = new ArrayList<>();
            for (int j : set) {
                list.add(j + arr[i]);
                max = Math.max(max, j + arr[i]);
            }
            for (int num : list) {
                map.put(num, 1);
            }
            map.put(arr[i], 1);
        }
        return max + 1;
    }
}

发表于 2018-05-21 18:47:59 回复(0)
童珉头像 童珉 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int n; cin>>n;

    vector<int> data; int tmp;
    for(int i=0; i<n; i++){cin>>tmp; data.push_back(tmp);}
    sort(data.begin(), data.end());

    if(data[0]!=1){cout<<1<<endl; return 0;}
    int res = 1;
    for(int i=1; i<data.size(); i++){
        if(data[i]<=res+1) res+=data[i];
        if(data[i]>res+1) break;
    }
    cout<<res+1<<endl;

    return 0;
}

编辑于 2018-04-17 10:57:05 回复(0)
C/C++
nbgao头像 nbgao 
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{     int n,a[30],m=0;     cin>>n;     for(int i=0;i<n;i++)         cin>>a[i];     sort(a,a+n);     for(int i=0;i<n;i++)     {         if(a[i]>m+1)             break;         m += a[i];     }     cout<<m+1<<endl;     return 0;
}

发表于 2018-01-12 01:27:36 回复(0)
C/C++
还哈哈头像 还哈哈 
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <limits>
using namespace std;
/*参考了 牛客470556号 的思想
有数列a1~an升序排列
设a1~ai 可以组成数字 1~m
则a(i+1)-1<=m
因为a1~a(i+1)即a1~ai~a(i+1),显然可以组成{a(i+1)、a(i+1)+1、a(i+1)+2、...、a(i+1)+m}中任意一个数，最小的就是a(i+1)
所以a(i+1)不能大于（m+1），否则就会出现空档，即无法组成的数字
*/
int main() {
	int n;
	cin >> n;
	map<int, int> m;
	for(int i=0;i<n;i++)
	{
		int tmp;
		cin >> tmp;
		m[tmp] += 1;
	}
	map<int, int>::iterator it = m.begin();
	int max;
	if (it->first > 1)
		max = 0;
	else
	{
		max = (it->first)*(it->second);
		for (it++; it != m.end(); it++)
		{
			if (max >= ((it->first) - 1))
				max += (it->first)*(it->second);
			else
				break;
		}
	}
	cout << ++max;
	return 0;
}

发表于 2017-09-03 10:53:08 回复(0)
C/C++
卡玛酱头像 卡玛酱 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
	int i,j,n,temp;
	vector<int> v;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>temp;
		v.push_back(temp);
	}
	sort(v.begin(),v.end());
	long long int sum=0;
	for(j=0;j<v.size();j++){
		if(v[j]>sum+1){
			break;
		}else{
			sum+=v[j];
		}
	}
	cout<<sum+1<<endl;
	return 0;
}

发表于 2017-08-24 21:36:14 回复(0)
提交观点

问题信息

数学 排序
来自：网易2017内推笔试编...
难度：
86条回答 24560浏览

热门推荐

通过挑战的用户

查看代码

相关试题

数字游戏

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号