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

通过软盘拷贝文件

问题描述

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

已知:

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

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

输入格式

第一行包含一个整数 $N$ ,表示计算机中的文件数量。 $1 \leq N \leq 1000$ 。

接下来 $N$ 行,每行包含一个整数 $S_i$ ,表示第 $i$ 个文件的大小(单位:字节)。 $0 \leq i < N, 0 \leq S_i$ 。

输出格式

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

样例输入

样例输出

样例解释

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

样例输入

样例输出

样例解释

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

数据范围

$1 \leq N \leq 1000$
$0 \leq S_i$

题解

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

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

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

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

解题步骤:

读入所有文件的大小。
创建一个动态规划数组 dp,其中 dp[i] 表示容量为 i 时可以存储的最大文件总大小。
遍历每个文件,对于每个文件,更新 dp 数组。
最终 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])

#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 = 0; i < n; i++) {
        scanf("%d", &files[i]);
    }

    // 动态规划过程
    for (i = 0; i < n; i++) {
        int blocks = (files[i] + 511) / 512;
        for (j = CAPACITY; j >= blocks; j--) {
            dp[j] = max(dp[j], dp[j - blocks] + files[i]);
        }
    }

    // 输出结果
    printf("%d\n", dp[CAPACITY]);

    return 0;
}

Javascript

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let n = 0;
let files = [];
const CAPACITY = 1474560 / 512;

rl.on('line', (line) => {
    if (n === 0) {
        n = parseInt(line);
    } else {
        files.push(parseInt(line));
        if (files.length === n) {
            solve();
            rl.close();
        }
    }
});

function solve() {
    // 创建动态规划数组
    let dp = new Array(CAPACITY + 1).fill(0);

    // 动态规划过程
    for (let file of files) {
        let blocks = Math.floor((file + 511) / 512);
        for (let i = CAPACITY; i >= blocks; i--) {
            dp[i] = Math.max(dp[i], dp[i - blocks] + file);
        }
    }

    // 输出结果
    console.log(dp[CAPACITY]);
}

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[] files = new int[n];
        for (int i = 0; i < n; i++) {
            files[i] = scanner.nextInt();
        }
        
        // 软盘容量（以块为单位）
        final int CAPACITY = 1474560 / 512;
        
        // 创建动态规划数组
        int[] dp = new int[CAPACITY + 1];
        
        // 动态规划过程
        for (int file : files) {
            int blocks = (file + 511) / 512;
            for (int i = CAPACITY; i >= blocks; i--) {
                dp[i] = Math.max(dp[i], dp[i - blocks] + file);
            }
        }
        
        // 输出结果
        System.out.println(dp[CAPACITY]);
        
        scanner.close();
    }
}

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

using namespace std;

const int CAPACITY = 1474560 / 512;

int main() {
    int n;
    cin >> n;
    
    vector<int> files(n);
    for (int i = 0; i < n; i++) {
        cin >> files[i];
    }
    
    // 创建动态规划数组
    vector<int> dp(CAPACITY + 1, 0);
    
    // 动态规划过程
    for (int file : files) {
        int blocks = (file + 511) / 512;
        for (int i = CAPACITY; i >= blocks; i--) {
            dp[i] = max(dp[i], dp[i - blocks] + file);
        }
    }
    
    // 输出结果
    cout << dp[CAPACITY] << endl;
    
    return 0;
}

#OD##机考##E卷#

OD刷题笔记文章被收录于专栏

本专栏收集并整理了一些刷题笔记