首页 > 试题广场 >

数字游戏

[编程题]数字游戏

热度指数：21450 时间限制：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个数x_i (1 ≤ x_i ≤ 100000)

输出描述:

输出最小不能由n个数选取求和组成的数

示例1

输入

3
5 1 2

输出

算法知识视频讲解

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)

小伟成

根据第一个回答,整理一下
假设排序后前 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

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

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勿忘初心

//将数组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)

牛客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

先对数组排序，记前n项和为S_n。然后遍历检查第i个数与S_i-1的差距是否不超过1，如果差距比1大，说明不连续，存在空档，S_i-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

 先排序
 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

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)

童珉

参考https://blog.csdn.net/tingyun_say/article/details/52425424

#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

#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)

wangwenbin

//最笨的方法，把所有的和计算出来，然后不能求和的
// 注意：相同的数字的处理
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int[] num = new int[n];
    		int sum = 0;
            for(int i=0;i<n;i++){
                num[i] = sc.nextInt();
                sum += num[i];
            }
            boolean[] s = new boolean[sum+1];
            boolean flag = false;
            for(int i=0;i<n;i++){
                if(s[num[i]]){
                    flag = true;
                }else{
                    s[num[i]] = true;
                }
                for(int j=sum;j>=0;j--){
                    if(flag){
                        if(s[j])s[j+num[i]]=true;
                    }else{
                        if(j!=num[i] && s[j])s[j+num[i]]=true;
                    }
                }
                flag = false;
            }
            flag = false;
            int min = 1;
            for(;min<=sum;min++){
                if(!s[min]){
                    break;
                }
            }
            if(min==sum+1){
            	System.out.println(sum+1);
            }else{
                System.out.println(min);
            }
        }
    }
}

发表于 2017-08-20 20:07:17 回复(1)

Java

Sevenid

从小到大排序，如果前面i个数的和比第i+1个数小2或者更多，就意味着拼死也无法表示(第i+1个数)-1，如果可以表示，则继续往下求和、比较；这里有个特殊情况，就是1，如果输入的最小的比1大，那对方直接说1，就没法表示了。。。

import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
//输入
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        int[] nums = new int[count];
        for (int i = 0; i < count; i++) {
            nums[i] = sc.nextInt();
        }
//排序
        Arrays.sort(nums);
//特例，没有1直接输出1
        if (nums[0] > 1) {
            System.out.println(1);
            return;
        }
//依次求和
        int sum = 0;
        for (int i = 0; i < count - 1; i++) {
            sum += nums[i];
            if (sum + 1 < nums[i + 1]){
                System.out.println(sum + 1);
                return;
            }
        }
        System.out.println(sum + nums[count - 1] + 1);
    }
}

发表于 2017-08-17 17:21:17 回复(0)

菜鸟四号

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,a[20],num=0;
    scanf("%d",&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]>num+1)
             break;
         num+=a[i];
     }
          cout<<num+1<<endl;
    return 0;
}

发表于 2017-08-09 10:07:06 回复(1)

toraoh

Google出过的原题……

http://code.google.com/codejam/contest/4244486/dashboard#s=p2

（需要***查看）

呃，这个题不知道见过几次了，自从google出过一次之后，之后忘了哪里又出了这个弱化版本，现在网易再出一次弱化版本，一点意思都没了……

Google提供的官方题解在：http://code.google.com/codejam/contest/4244486/dashboard#s=a&a=2

中文简单转述：

从小到大排序，一开始一块钱都凑不出来

下面，为了0~x都有，我需要来一个1元的（不然1元凑不出来）

给了你1元的，下面必须给1+1元以内的，不然2元凑不出来

如果再给一个1元的，那你现在能凑出0~2元的，接下来+1+2或者+3，都能增大范围而且不会导致中间缺一个数（4元的不行，因为凑不出3了）

——反正一直往下，直到出现第一个算不出来的值为止。

听说考试的时候n=100，现在练习改20，不知道什么心态——当时约4000人中有约400人通过了，说明n=100的时候筛选能力就很好啊……

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;

int a[1005];

int main(){
    int miss=0;
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    sort(a,a+n);
    for(int i=0;i<n;i++){
        if(a[i]>miss+1) break;
        miss+=a[i];
    }
    printf("%d\n",miss+1);
    return 0;
}

——同学们啊，请一定要做Google出的题目，codejam可能要求高一点（这题是codejam round1的C题），但是至少APAC Test要做一做——你看google前一年出了一个01字典树，微软第二年校招实习笔试也出了一个，现在再加上网易又来一出——简直是校招笔试编程题风向标。

发表于 2016-08-08 19:13:56 回复(21)