E卷-通过软盘拷贝文件(200分)

通过软盘拷贝文件

问题描述

一位科学家正在研究一台古董电脑中的文件。这台电脑只有一个 3.5 寸软盘驱动器可以用来拷贝文件,而且只有一张软盘可用。科学家希望能够最大化地利用这张软盘,将尽可能多的文件内容拷贝出来。

已知:

1. 软盘容量为 1474560 字节。
2. 文件在软盘上按块分配空间,每块大小为 512 字节。
3. 一个块只能被一个文件使用。
4. 拷贝到软盘中的文件必须是完整的,不能采取任何压缩技术。
5. 为了充分利用软盘空间,文件在软盘上实际占用的块数会被记录下来,不计入软盘使用空间。

科学家的目标是使拷贝到软盘中的文件内容总大小最大。请你帮助科学家计算出能够拷贝的最大文件总大小。

输入格式

第一行包含一个整数 ,表示计算机中的文件数量。。

接下来 行,每行包含一个整数 ,表示第 个文件的大小(单位:字节)。。

输出格式

输出一个整数,表示科学家最多能拷贝的文件总大小(单位:字节)。

样例输入

3
737270
737272
737288

样例输出

1474542

样例解释

3 个文件中,每个文件实际占用的大小分别为 737280 字节、737280 字节、737792 字节。只能选取前两个文件,总大小为 1474542 字节。虽然后两个文件总大小更大且未超过 1474560 字节,但因为实际占用的大小超过了 1474560 字节,所以不能选后两个文件。

样例输入

6
400000
200000
200000
200000
400000
400000

样例输出

1400000

样例解释

从 6 个文件中,选择 3 个大小为 400000 的文件和 1 个大小为 200000 的文件,得到最大总大小为 1400000。也可以选择 2 个大小为 400000 的文件和 3 个大小为 200000 的文件,得到的总大小也是 1400000。

数据范围

题解

这道题目本质上是一个变形的 0-1 背包问题。

需要从给定的文件中选择一些,使得它们的总大小不超过软盘容量,同时尽可能地大。

关键点在于理解文件在软盘上的存储方式。每个文件占用的空间都是 512 字节的整数倍，但我们只需要考虑文件的实际大小。

这意味着我们可以直接使用文件的原始大小进行计算,而不需要考虑向上取整到 512 的倍数。

解题步骤:

1. 读入所有文件的大小。
2. 创建一个动态规划数组 dp,其中 dp[i] 表示容量为 i 时可以存储的最大文件总大小。
3. 遍历每个文件,对于每个文件,更新 dp 数组。
4. 最终 dp[1474560 / 512] 就是我们要求的答案。

• Python

# 读取输入
n = int(input())  # 文件数量
files = [int(input()) for _ in range(n)]  # 每个文件的大小

# 软盘容量（以块为单位）
CAPACITY = 1474560 // 512

# 创建动态规划数组
dp = [0] * (CAPACITY + 1)

# 动态规划过程
for file in files:
    # 计算文件占用的块数
    blocks = (file + 511) // 512
    # 从大到小遍历容量,避免重复计算
    for i in range(CAPACITY, blocks - 1, -1):
        # 选择不拷贝该文件或拷贝该文件,取较大值
        dp[i] = max(dp[i], dp[i - blocks] + file)

# 输出结果
print(dp[CAPACITY])

• C

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000
#define CAPACITY 2880  // 1474560 / 512

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, i, j;
    int files[MAX_N];
    int dp[CAPACITY + 1] = {0};

    // 读取输入
    scanf("%d", &n);
    for (i =