正数数组的最小不可组成和-进阶问题

[编程题]正数数组的最小不可组成和-进阶问题

热度指数：736 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个正数数组arr，其中所有的值都为整数，以下是最小不可组成和的概念

把arr每个子集内的所有元素加起来会出现很多值，其中最小的记为min，最大的记为max
在区间[min, max]上，如果有数不可以被arr某一个子集相加得到，那么其中最小的那个数是arr的最小不可组成和
在区间[min, max]上，如果所有的数都可以被arr的某一个子集相加得到，那么max+1是arr的最小不可组成和

请写函数返回正数数组arr的最小不可组成和

保证1一定出现过！

时间复杂度为，额外空间复杂度为

输入描述:

第一行一个整数N，表示数组长度。
接下来一行N个整数表示数组内的元素。

输出描述:

输出一个整数表示数组的最小不可组成和

示例1

输入

3
1 2 5

输出

说明

3 = 1 + 2

示例2

输入

5
1 2 3 4 5

输出

备注:

算法知识视频讲解

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    priority_queue<int, vector<int>, greater<int>> q;
    int n, x;
    long s=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        q.push(x);
    }
    while(!q.empty()){
        x = q.top();
        q.pop();
        if(s+1 >= x)
            s += x;
        else
            break;
    }
    cout<<s+1<<endl;
    return 0;
}

发表于 2020-03-30 00:51:34 回复(1)