我要招人

去企业版

首页 > 试题广场 >

贪心的小博

[编程题]贪心的小博

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

小博沉迷收集卡片，购买干脆面是他收集卡片的主要方式。他总共渴望的有 N 类卡片，均可通过购买干脆面获得，一包干脆面中有且仅有一张卡片，并且卡片类型对应N类卡片中的一种。且每种类型的卡片出现在一包干脆面中的概率是相等的。

小博非常的贪心，他有 N 个愿望，第i个愿望即为:拥有至少 p_i 张i类卡片，其中 1 ≤ i ≤ N。

然而，小博又极其贫困，他想知道最少需要买多少干脆面，使得在最坏情况下，至少能够满足他 N 个愿望的其中一个。

数据范围： $1 \le n \le 10^5\$ ， $1 \le p_i \le 10^5 \$

输入描述:

第一行包含一个整数 N 。
接下来的N行，每行一个整数pi，pi表示小博希望至少拥有的i类卡片数量。。

输出描述:

输出一个整数ANS，小博可以完成至少一个愿望需要购买的最少的干脆面的数量。

示例1

输入

输出

示例2

输入

2
3
5

输出

算法知识视频讲解

向宇回桌

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    long long ans = 0;
    for (int i=0; i<n; i++) {
        int tmp; cin >> tmp;
        ans += (tmp - 1);
    }
    cout << ans + 1<< endl;
    return 0;
}

发表于 2019-04-23 13:37:27 回复(2)

pein531

最坏的情况就是每种卡片都还差一张集齐，再买一包干脆面就一定可以集齐一种卡片，此时要买的干脆面包数为p1+...+pi+...+pn-n+1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long sum = 0;
        for(int i = 0; i < n; i++) sum += sc.nextInt();
        // 最坏情况：买了sum-n包仍然每种都还差一个，那么再买一包一定有一种卡片能够集齐
        System.out.println(sum - n + 1);
    }
}

发表于 2021-02-03 18:19:56 回复(0)

无心2019

#include <bits/stdc++.h>
using namespace std; 
int main()
{
    int n,p[100001];
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>p[i];
    long long res=0;
    for(int i=0;i<n;i++)
        res=res+p[i]-1;
    cout<<res+1<<endl;
    return 0;
}

发表于 2019-06-18 09:25:21 回复(0)

wylu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
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());
        long sum = 0;
        for (int i = 0; i < n; i++) sum += Integer.parseInt(br.readLine());
        System.out.println(sum - (n - 1));
    }
}

发表于 2019-03-13 20:39:11 回复(0)

hzpzlz1314

#include<iostream>
#include<vector>
using namespace std;
int main(){
    long n;
    while(cin>>n){
        vector<int>data(n);
        long sum=0;
        for(int i=0;i<n;i++){
            cin>>data[i];
            sum+=data[i];
        }
        cout<<sum-n+1<<endl;
    }
    return 0;
}

//注意用long 用int只AC 90%

发表于 2019-04-12 22:23:53 回复(0)

C/C++

茶月猫

最惨的情况就是每种卡片都收集到差了一张，然后又买了一包，就集齐了某种。读题以为是个多难的题目，实际上三行代码，关键还是理解的问题。不需要数组存储，直接计算就行。

#include <iostream>
using namespace std;
int main(void)
{
    int N;
    cin >> N;
    long long sum = 0;
    for (int i = 0; i < N; i++)
    {
        int temp;
        cin >> temp;
        sum += temp;
    }
    cout << sum - N + 1 << endl;
    return 0;
}

发表于 2019-07-21 21:34:24 回复(0)

黄宗文

def dream(n):
    res = 0
    for i in range(n):
        res += int(input())   # 题目描述有问题，期望卡片数是分在多行输入的
    return res - n + 1   # 每种卡片都达到最大值减一个，额外加一

if __name__ == "__main__":
    n = int(input())
    print(dream(n))

发表于 2019-03-25 14:35:32 回复(0)

科技a

var readline = require("readline");

const r1 = readline.createInterface({

input: process.stdin,

output: process.stdout,

});

const lines = [];

r1.on("line", function (line) {

lines.push(line);

if (lines.length === 2) {

const N =Number(lines[0]);

const pi = ( lines[1].split(" "));

let amount=0;

pi.map(item=>{

amount+=Number(item);

})

console.log(amount-N+1);

}

});

发表于 2023-09-19 11:53:25 回复(0)

Python3

筱伞不是伞！

推测有一个输入用了多个换行符，换了个输入处理方式就过了

import sys

a = []
for line in sys.stdin:
    a += line.split()

count = 0
for i in range(1,int(len(a))):
    count += int(a[i]) -1

count = count+1
print(count)

发表于 2023-04-06 12:41:51 回复(0)

山涧雪

#include<stdio.h>
int main()
{
    long long kinds = 0;
    long long  p1= 0;
    long long sum = 1;
    scanf("%lld", &kinds);
    while(kinds)
    {
        kinds--;
        scanf("%lld", &p1);
        sum += p1-1;
    }
    printf("%lld\n", sum);
    return 0;
}

发表于 2021-10-05 11:42:54 回复(0)

C/C++

牛客549207409号

#include<iostream>
int main()
{
int N,pi;
while(std::cin>>N)
{
long long count=0;
for(int i=0;i<N;i++)
{
std::cin>>pi;
count+=pi;
}
std::cout<<count-N+1<<std::endl;
}
return 0;
}就是道小学奥数题

发表于 2020-09-14 23:39:37 回复(0)

柠檬小精灵

n = int(input())

a = 0
for i in range(n):
    a += int(input())

f = a - n + 1
print(f)

发表于 2020-06-27 10:58:40 回复(0)

Shelven丶

#include<bits/stdc++.h>

using namespace std;

int main()
{
	long long z;
	cin >> z;
	long long zz = z, sum = 0;
	while (zz--)
	{
		long long c;
		cin >> c;
		sum += c;
	}
	cout << sum - z + 1;
}

发表于 2020-04-11 14:32:11 回复(0)

渡口的小太阳

我只想说，小博这样也太惨了

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long count=1;
        for(int i=0;i<n;i++){
            count+=sc.nextInt()-1;
        }
        System.out.println(count);
    }
}

发表于 2019-06-05 21:11:40 回复(0)

ID84848484

那位大佬看一下，为什么报错：请检查是否存在数组越界等非法访问情况

import java.util.*;
import java.io.*;

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());
        String[] str=br.readLine().split(" ");
        //Scanner in=new Scanner(System.in);
        //int n=in.nextInt();
        long ret=0;
        for(int i=0;i<n;i++){
            ret+=Integer.parseInt(str[i]);
            //ret+=in.nextInt();
        }
        System.out.println(ret-n+1);
    }
}

发表于 2019-04-20 14:48:17 回复(1)

没有意外

import sys
n=int(sys.stdin.readline().strip())
result=[]
for i in range(n):
    m=list(map(int,sys.stdin.readline().strip().split()))
    for j in m:
        result.append(j-1)
print(sum(result)+1)

发表于 2019-04-06 20:30:12 回复(0)