首页 > 试题广场 >

累加出整个范围所有的数最少还需要几个数

[编程题]累加出整个范围所有的数最少还需要几个数
  • 热度指数:833 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个正数数组 和一个正数,可以选择 中的任意个数字加起来的和为
返回最小需要往 中添加几个数,使得 可以取到范围上的每一个数。
给出的数组不保证有序!

输入描述:
第一行一个整数N, K。表示数组长度以及range
接下来一行N个整数表示数组内的元素


输出描述:
输出一个整数表示答案
示例1

输入

4 15
1 2 3 7

输出

1

说明

想累加得到范围上的所有的数,arr还缺14这个数,所以返回1 
示例2

输入

3 14
1 5 7

输出

2

说明

想累加得到1~14范围上所有的数,arr还缺2和4,所以返回2。 

备注:


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

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

发表于 2020-04-05 03:21:06 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, range;
    scanf("%d%d", &n, &range);
    vector<int> arr(n);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    sort(arr.begin(), arr.end()); //想了下,用小根堆的话可以省掉排序时间O(N)
    int need = 0;  //缺少几个数字
    int touch = 0; //完成1-torch
    for(int i=0; i<n; i++){
        while(arr[i] > touch+1){
            need++;
            touch += (touch+1);
        }
        touch += arr[i];
        if(touch >= range) break;
    }
    while(touch < range){
        touch += (touch + 1);
        need++;
    }
    printf("%d", need);
    return 0;
}

发表于 2020-02-09 17:21:53 回复(0)
import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        System.out.print(minNeed(arr,k));
    }
    public static int minNeed(int[] arr,int range){
        Arrays.sort(arr);
        int need=0;
        int touch=0;
        for(int i=0;i<arr.length;i++){
            while(arr[i]>touch+1){
                touch+=touch+1;
                need++;
                if(touch>=range){
                    return need;
                    
                }
            }
            touch+=arr[i];
            if(touch>=range){
                return need;
            }
        }
        while(range>=touch+1){
            touch+=touch+1;
            need++;
        }
        return need;
    }
}

发表于 2021-03-25 10:45:41 回复(0)