【贪心】2023B-数据最节约的备份方法

[P3116] 【贪心】2023B-数据最节约的备份方法

本题练习地址：https://www.algomooc.com/problem/P3116

直播回看地址：2023/11/18 真题讲解

题目描述与示例

题目描述

有若干个文件，使用刻录光盘的方式进行备份，假设每张光盘的容量是500MB，求使用光盘最少的文件分布****方式

所有文件的大小都是整数的MB，且不超过500MB;

文件不能分割、分卷打包。

输入描述

一组文件大小的数据

输出描述

使用光盘的数量。

备注不用考虑输入数据不合法的情况

假设最多100个输入文件。

示例一

输入

100,500,300,200,400

输出

说明

(100,400),(200,300),(500)

3张光盘即可。

输入和输出内容都不含空格。

示例二

输入

100,100,200,300

输出

解题思路

为了尽可能少地使用光盘，我们贪心地希望一张光盘所使用的容量尽可能地满，所以每一次选择的时候，我们总是优先选择大的数据进行填充，这样才能使得每一张光盘的剩余空间尽可能地小。

因此，我们需要先对数组nums进行降序排序，然后构建一个长度为n的check数组，用来记录第i个数据是否已经存入某张光盘中。即

nums = list(map(int, input().split(",")))
nums.sort(reverse = True)
n = len(nums)
ans = 0
check = [0] * n

然后我们从大到小（即从前往后）遍历所有数据nums[i]，若

nums[i]如果已经存入光盘中，即check[i] == 1，则可以直接跳过
nums[i]如果尚未存入光盘中，即check[i] == 0，则需要使用一张全新的光盘来储存包含nums[i]的数据，同时进行内层循环，贪心地用剩余的较大数据填充这张光盘。

显然这里需要两个变量i和j，涉及到了同向双指针。

for i in range(n):
    if check[i] == 1:
        continue
    ans += 1
    cur_sum = 0
    j = i
    while j < n:
        if check[j] == 1:
            j += 1
            continue
        if nums[j] + cur_sum > 500:
            j += 1
        else:
            cur_sum += nums[j]
            check[j] = 1
            j += 1

代码

Python

# 题目：【贪心】2023B-数据最节约的备份方法
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：贪心
# 代码看不懂的地方，请直接在群上提问


# 输入数据并且进行降序排序
nums = list(map(int, input().split(",")))
nums.sort(reverse = True)
# 获得nums的长度
n = len(nums)
# 初始化答案变量ans
ans = 0
# 初始化长度为n的check数组，用来表示第i个数据是否已经存入光盘中
check = [0] * n

# 遍历所有数据
for i in range(n):
    # 如果已经存入光盘中，则可以直接跳过
    if check[i] == 1:
        continue
    # 否则，需要一张新的光盘
    # 来存放包含数据nums[i]在内的若干数据
    # 故ans更新
    ans += 1
    # 初始化当前这一张光盘的使用情况为0
    # 即当前这一张光盘储存的文件大小的总和
    cur_sum = 0
    # 初始化变量j为i，用于修改当前这一张光盘的使用情况
    j = i
    # 进行内层循环，此处涉及贪心算法
    while j < n:
        # 如果第j份数据已经检查过，则j直接递增，
        # 直接跳过后续逻辑，进入下个循环
        if check[j] == 1:
            j += 1
            continue
        # 如果第j份数据和当前光盘使用情况之和超过500
        # 则不能选择第j份数据进入光盘，j递增
        if nums[j] + cur_sum > 500:
            j += 1
        # 如果第j份数据和当前光盘使用情况之和不超过500
        # 则选择第j份数据进入光盘，
        # 修改cur_sum和check[j]，j递增
        else:
            cur_sum += nums[j]
            check[j] = 1
            j += 1

print(ans)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(",");
        int[] nums = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            nums[i] = Integer.parseInt(input[i]);
        }
        scanner.close();

        // Sorting in descending order
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] < nums[j]) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }

        int n = nums.length;
        int ans = 0;
        int[] check = new int[n];

        for (int i = 0; i < n; i++) {
            if (check[i] == 1) {
                continue;
            }
            ans += 1;
            int curSum = 0;
            int j = i;
            while (j < n) {
                if (check[j] == 1) {
                    j += 1;
                    continue;
                }
                if (nums[j] + curSum > 500) {
                    j += 1;
                } else {
                    curSum += nums[j];
                    check[j] = 1;
                    j += 1;
                }
            }
        }

        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

int main() {
    string input;
    getline(cin, input);

    stringstream ss(input);
    string token;
    vector<int> nums;

    while (getline(ss, token, ',')) {
        int num = stoi(token);
        nums.push_back(num);
    }

    // Sorting in descending order
    sort(nums.begin(), nums.end(), greater<int>());

    int n = nums.size();
    int ans = 0;
    vector<int> check(n, 0);

    for (int i = 0; i < n; i++) {
        if (check[i] == 1) {
            continue;
        }
        ans += 1;
        int curSum = 0;
        int j = i;
        while (j < n) {
            if (check[j] == 1) {
                j += 1;
                continue;
            }
            if (nums[j] + curSum > 500) {
                j += 1;
            } else {
                curSum += nums[j];
                check[j] = 1;
                j += 1;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

时空复杂度

时间复杂度：O(N^2)。需要进行双重循环遍历，由于数据量很小最多仅为100，故该算法可以通过所有用例。

空间复杂度：O(N)。check数组所占空间。