小美明天要去春游了。她非常喜欢吃巧克力，希望能够带尽可能多的巧克力在春游的路上吃。她现在有n个巧克力，很巧的是她所有的巧克力都是厚度一样的正方形的巧克力板，这n个巧克力板的边长分别为ag,a2…3n。因为都是厚度一致的正方形巧克力板，我们认为第1个巧克力的重量为a?.小美现在准备挑选一个合适大小的包来装尽可能多的巧克力板，她十分需要你的帮助来在明天之前准备完成，请你帮帮她。

思路：二分答案+贪心

本题可以使用二分答案的思路。我们可以二分一个范围，来判断能否在这个范围内选择一个合适大小的包来装下所有的巧克力板。具体的，我们可以二分巧克力板的边长之和的一半，即巧克力板能够装进去的包的大小的上限。然后我们可以写一个函数check(mid)，用来判断在包大小为mid的情况下，能否装下所有的巧克力板。这个函数可以贪心地来实现，我们可以按照巧克力板边长从大到小排序，然后依次将巧克力板放进包里。如果发现已经装不下了，就返回false，否则返回true即可。

最后，我们可以使用二分答案的方式来不断缩小范围，直到找到满足要求的最大包大小。

AC Code:

相关问题

用cpp写出：小美是一位天文爱好者，她收集了接下来一段时间中所有会划过她所在的观测地上空的流星信息。具体地，她收集了n个流星在她所在观测地上空的出现时刻和消失时刻。对于一个流星，若其的出现时刻为s，消失时刻为t，那么小美在时间段[s, t]都能够观测到它。对于一个时刻，观测地上空出现的流星数量越多，则小美认为该时刻越好。小美希望能够选择一个最佳的时刻进行观测和摄影，使她能观测到最多数量的流星。现在小美想知道，在这个最佳时刻，她最多能观测到多少个流星以及一共有多少个最佳时刻可供她选择

以下是用C++实现的代码：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> s(n), t(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i] >> t[i];
    }

    int maxCount = 0, count = 0;
    vector<int> bestTimes;
    for (int i = 0; i < n; i++) {
        count = 1;
        for (int j = 0; j < n; j++) {
            if (i != j && s[j] <= s[i] && t[j] >= s[i]) {
                count++;
            }
        }
        if (count > maxCount) {
            maxCount = count;
            bestTimes.clear();
            bestTimes.push_back(s[i]);
        } else if (count == maxCount) {
            bestTimes.push_back(s[i]);
        }
    }
    cout << maxCount << " " << bestTimes.size() << endl;
    return 0;
}

代码思路：

1. 读入n个流星的出现时刻和消失时刻。
2. 遍历每个时刻，统计当前时刻的流星数量。
3. 如果当前时刻的流星数量大于最大流星数量，更新最大流星数量和最佳时刻列表。
4. 如果当前时刻的流星数量等于最大流星数量，将当前时刻添加到最佳时刻列表中。
5. 输出最大流星数量和最佳时刻个数。

用java写出：小美是一位天文爱好者，她收集了接下来一段时间中所有会划过她所在的观测地上空的流星信息。具体地，她收集了n个流星在她所在观测地上空的出现时刻和消失时刻。对于一个流星，若其的出现时刻为s，消失时刻为t，那么小美在时间段[s, t]都能够观测到它。对于一个时刻，观测地上空出现的流星数量越多，则小美认为该时刻越好。小美希望能够选择一个最佳的时刻进行观测和摄影，使她能观测到最多数量的流星。现在小美想知道，在这个最佳时刻，她最多能观测到多少个流星以及一共有多少个最佳时刻可供她选择。

以下是使用Java语言实现的代码：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] meteors = new int[n][2];
        for (int i = 0; i < n; i++) {
            meteors[i][0] = scanner.nextInt();
            meteors[i][1] = scanner.nextInt();
        }
        int maxNum = 0;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int num = 0;
            for (int j = 0; j < n; j++) {
                if (meteors[j][0] <= meteors[i][1] && meteors[j][1] >= meteors[i][0]) {
                    num++;
                }
            }
            if (num > maxNum) {
                maxNum = num;
                cnt = 1;
            } else if (num == maxNum) {
                cnt++;
            }
        }
        System.out.println(maxNum + " " + cnt);
    }
}

程序首先读入流星数量n以及每个流星的出现时刻和消失时刻。然后，使用两个嵌套循环遍历所有流星，统计每个流星出现时刻到消失时刻内的其他流星数量。最后，找到最多的流星数量以及出现次数，并输出结果。