E卷-通过软盘拷贝文件(200分)
通过软盘拷贝文件
问题描述
一位科学家正在研究一台古董电脑中的文件。这台电脑只有一个 3.5 寸软盘驱动器可以用来拷贝文件,而且只有一张软盘可用。科学家希望能够最大化地利用这张软盘,将尽可能多的文件内容拷贝出来。
已知:
- 软盘容量为 1474560 字节。
- 文件在软盘上按块分配空间,每块大小为 512 字节。
- 一个块只能被一个文件使用。
- 拷贝到软盘中的文件必须是完整的,不能采取任何压缩技术。
- 为了充分利用软盘空间,文件在软盘上实际占用的块数会被记录下来,不计入软盘使用空间。
科学家的目标是使拷贝到软盘中的文件内容总大小最大。请你帮助科学家计算出能够拷贝的最大文件总大小。
输入格式
第一行包含一个整数 ,表示计算机中的文件数量。。
接下来 行,每行包含一个整数 ,表示第 个文件的大小(单位:字节)。。
输出格式
输出一个整数,表示科学家最多能拷贝的文件总大小(单位:字节)。
样例输入
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 的倍数。
解题步骤:
- 读入所有文件的大小。
- 创建一个动态规划数组 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])
- 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 = 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();
}
}
- Cpp
#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卷#本专栏收集并整理了一些刷题笔记