[已解决]梦想星际舰队第17关 && FCOI #8 第四题果篮题解【原创】

zhangjinxuan

梦想星际舰队第17关 && FCOI #8 题解

第四题：果篮

题目描述
有 N 个果篮，第 i 个果篮最多只能装下 Ai kg 的水果，现在要用一个或多个果篮来装这 V kg 的水果，问至少需要多少果篮？

如果用上所有的果篮都装不下，输出 -1。

输入格式
第一行两个整数 N,V

第二行 N 个数字，第 i 个数字表示 Ai ，也就是第 i 个果篮的最大容量。

输出格式
一个整数表示至少需要的果篮数，或者 -1。

输入输出样例
输入 #1

1. 3 5
   
2. 4 3 2

复制代码

输出 #1

1. 2

复制代码

输入 #2

1. 3 5
   
2. 1 1 1

复制代码

输出 #2

1. -1

复制代码

输入 #3

1. 5 25
   
2. 13 9 8 6 3

复制代码

输出 #3

1. 3

复制代码

数据范围

对于 100% 的数据，保证 1≤N≤2×10^5 ,1≤A i≤10^9,1≤V≤10^12

其他说明
本题目为 zhangjinxuan 原创题目。
测试链接：https://www.luogu.com.cn/problem/U325232

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳战士排行榜

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-8-23 20:12:20

1. a,b=map(int,input().split())
   
2. c = list(map(int,input().split()))
   
3. c.sort(reverse=True)
   
4. d = 0
   
5. e=0
   
6. if sum(c) < b:
   
7.     print(-1)
   
8. else:
   
9.     for i in range(a):
   
10.         d += c[e]
    
11.         if d>b:
    
12.             print(e+1)
    
13.             break
    
14.         e+=1
    
15.         

复制代码

这道题随便写个暴力就能过，真好

跳转到最佳答案楼层

isdkz

题目要求根据给定的果篮容量和需要装的水果重量，计算至少需要多少个果篮。如果无法装下所有水果，则输出-1。

解题思路：
1. 首先，对果篮的容量进行排序，从小到大。
2. 从容量最小的果篮开始，依次累加容量，直到累加的容量大于等于需要装的水果重量V。
3. 如果累加的容量大于等于V，则输出当前使用的果篮数量。
4. 如果累加的容量小于V，但已经使用了所有的果篮，则输出-1。

代码实现如下：

1. import java.util.Arrays;
   
2. import java.util.Scanner;
   
3. 
   
4. public class Main {
   
5.     public static void main(String[] args) {
   
6.         Scanner scanner = new Scanner(System.in);
   
7.         int N = scanner.nextInt();
   
8.         long V = scanner.nextLong();
   
9.         long[] baskets = new long[N];
   
10.         for (int i = 0; i < N; i++) {
    
11.             baskets[ i] = scanner.nextLong();
    
12.         }
    
13.         Arrays.sort(baskets); // 对果篮容量进行排序
    
14. 
    
15.         long sum = 0; // 累加的容量
    
16.         int count = 0; // 使用的果篮数量
    
17.         for (int i = 0; i < N; i++) {
    
18.             sum += baskets[ i];
    
19.             count++;
    
20.             if (sum >= V) {
    
21.                 System.out.println(count);
    
22.                 return;
    
23.             }
    
24.         }
    
25.         System.out.println(-1);
    
26.     }
    
27. }
    

复制代码

时间复杂度分析：
对果篮容量进行排序的时间复杂度为O(NlogN)，遍历果篮的时间复杂度为O(N)，因此总的时间复杂度为O(NlogN)。

空间复杂度分析：
除了输入和输出的空间，只需要额外的常数空间来保存果篮容量，因此空间复杂度为O(N)。

陶远航

根据您提供的题目描述，您需要编写一个程序来计算装下给定重量的水果所需的最少果篮数量。以下是一个可能的解决方案：

1. def min_baskets(N, V, capacities):
   
2.     capacities.sort()  # 将果篮容量从小到大排序
   
3.     total_baskets = 0
   
4.     remaining_weight = V
   
5. 
   
6.     for capacity in capacities:
   
7.         if remaining_weight <= 0:
   
8.             break
   
9.         if capacity >= remaining_weight:
   
10.             total_baskets += 1
    
11.             break
    
12.         else:
    
13.             total_baskets += 1
    
14.             remaining_weight -= capacity
    
15. 
    
16.     if remaining_weight > 0:
    
17.         return -1
    
18.     return total_baskets
    
19. 
    
20. # 读取输入
    
21. N, V = map(int, input().split())
    
22. capacities = list(map(int, input().split()))
    
23. 
    
24. # 计算并输出结果
    
25. result = min_baskets(N, V, capacities)
    
26. print(result)

复制代码

您可以使用上述 Python 代码来解决这个问题。首先，它将果篮容量从小到大排序，然后依次尝试将水果放入果篮，直到无法再放入为止。如果还有剩余的水果重量，说明所有果篮都无法容纳，返回 -1。否则，返回所需的果篮数量。

您可以将输入示例输入到程序中，然后程序会输出相应的结果。

zhangjinxuan

isdkz 发表于 2023-8-23 17:36
题目要求根据给定的果篮容量和需要装的水果重量，计算至少需要多少个果篮。如果无法装下所有水果，则输出-1 ...

《什么情况，居然错的》

tyh小号

zhangjinxuan 发表于 2023-8-23 17:37
《什么情况，居然错的》

看看我的

陶远航

tyh小号 发表于 2023-8-23 17:38
看看我的

支持！

陈尚涵

看看

zhangjinxuan

陶远航 发表于 2023-8-23 17:37
根据您提供的题目描述，您需要编写一个程序来计算装下给定重量的水果所需的最少果篮数量。以下是一个可能的 ...

证明贪心正确，不证明不给你

陶远航

zhangjinxuan 发表于 2023-8-23 17:51
证明贪心正确，不证明不给你

要证明贪心算法的正确性，需要考虑两个方面：贪心选择性质和最优子结构性质。

1. 贪心选择性质：贪心算法每一步都选择局部最优解，希望这些局部最优解最终能够构成全局最优解。在这个问题中，我们要尽量将水果放入剩余容量最大的果篮中，这样可以最大限度地减少所需的果篮数量。贪心选择性质在这里体现为，每次选择一个能够装下尽可能多水果的果篮。

2. 最优子结构性质：问题的最优解包含了子问题的最优解。在这个问题中，假设我们已经找到了装下剩余水果重量的最优果篮数量，如果我们将一个能够容纳更多水果的果篮替换为多个容量更小的果篮，那么替换后的解一定不会更优。因此，问题的最优解包含了子问题的最优解，这符合最优子结构性质。

综合上述两个性质，我们可以得出贪心算法在这个问题中的正确性。因为每次选择局部最优解，并且问题的最优解包含了子问题的最优解，所以贪心算法最终会得到全局最优解。

在这个问题中，贪心算法的思路是通过选择最大容量的果篮来尽可能多地装水果，然后继续选择次大容量的果篮，以此类推。这样的选择策略能够确保在给定限制下，使用最少的果篮数量。

sfqxx

陶远航 发表于 2023-8-23 17:54
要证明贪心算法的正确性，需要考虑两个方面：贪心选择性质和最优子结构性质。

1. 贪心选择性质：贪心 ...

错的

sfqxx

1. a,b=map(int,input().split())
   
2. c = list(map(int,input().split()))
   
3. c.sort(reverse=True)
   
4. d = 0
   
5. e=0
   
6. if sum(c) < b:
   
7.     print(-1)
   
8. else:
   
9.     for i in range(a):
   
10.         d += c[e]
    
11.         if d>b:
    
12.             print(e+1)
    
13.             break
    
14.         e+=1
    
15.         

复制代码

这道题随便写个暴力就能过，真好