题目描述
有一名科学家想要从一台古董电脑中拷贝文件到自己的电脑中加以研究但此电脑除了有一个3.5寸软盘驱动器以外,没有任何手段可以将文件持贝出来,而且只有一张软盘可以使用,因此这一张软盘是唯一可以用来拷贝文件的载体。
科学家想要尽可能多地将计算机中的信息拷贝到软盘中,做到软盘中文件内容总大小最大。已知该软盘容量为1474560字节。文件占用的软盘空间都是按块分配的,每个块大小为512个字节。一个块只能被一个文件使用。拷贝到软盘中的文件必须是完整的,且不能采取任何压缩技术。
输入描述
第1行为一个整数N,表示计算机中的文件数量。1≤ N < 1000。
第2行到第N+1行(共N行),每行为一个整数,表示每个文件的大小 s i s_i si,单位为字节.0 < i < N,0< s i s_i si< 1000000
输出描述
科学家最多能拷贝的文件总大小。
示例1
输入:
3
737270
737272
737288
输出:
1474542
题解
Java
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
// 软盘容量的块数
int BLOCK_VOLUME = 1474560 / 512;
Scanner scanner = new Scanner(System.in);
// 读取文件数量
int n = scanner.nextInt();
// 存储每个文件的大小
int[] sizes = new int[n];
for (int i = 0; i < n; i++) {
sizes[i] = scanner.nextInt();
}
int[] dp = new int[BLOCK_VOLUME + 1];
for (int size : sizes) {
int block = (int) Math.ceil((double) size / 512); // 存储文件所占的块数
for (int vol = BLOCK_VOLUME; vol >= block; vol--) {
dp[vol] = Math.max(dp[vol], dp[vol - block] + size);
}
}
System.out.println(dp[BLOCK_VOLUME]);
}
}
Python
# 软盘的块数
from math import ceil
# 软盘容量的块数
BLOCK_VOLUME = 1474560 // 512
n = int(input())
# 存储每个文件的大小
sizes = [int(input()) for _ in range(n)]
dp = [0] * (BLOCK_VOLUME + 1)
for size in sizes:
block = ceil(size / 512) # 存储文件所占的块数
for vol in range(BLOCK_VOLUME, block - 1, -1):
dp[vol] = max(dp[vol], dp[vol - block] + size)
print(dp[BLOCK_VOLUME])
C++
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 软盘容量的块数
const int BLOCK_VOLUME = 1474560 / 512;
int n;
cin >> n;
// 存储每个文件的大小
vector<int> sizes(n);
for (int i = 0; i < n; ++i) {
cin >> sizes[i];
}
// dp数组初始化
vector<int> dp(BLOCK_VOLUME + 1, 0);
for (int size : sizes) {
// 存储文件所占的块数
int block = (size - 1) / 512 + 1;
for (int vol = BLOCK_VOLUME; vol >= block; --vol) {
dp[vol] = max(dp[vol], dp[vol - block] + size);
}
}
cout << dp[BLOCK_VOLUME] << endl;
return 0;
}
相关练习题
🙏整理题解不易, 如果有帮助到您,请给点个赞 ❤️ 和收藏 ⭐,让更多的人看到。🙏🙏🙏