题目描述

最近塔子哥正在研究什么是虚拟化内存，于是塔子哥想自己亲自动手试一试，你能帮助他吗？

实现一个地址范围为32G，可在范围内任意位置进行数据读写的虚拟化内存机制，数据默认清零。 功能:

1. 读写任意地址数据；
2. 往任意地址写入任意数据；
3. 清空数据，并释放内存；

PS：一个地址空间存一个数据，各地址空间独立

输入描述

输入格式：Command Address Length Data

1、Command为Read、Write、Clear之一

2、Address采用64位无符号十六进制数，全大写

3、Length采用64位无符号十进制数，单位为“字节”

4、Data采用字节流(2个16进制数表示一个Byte)，全大写;

5、如果指定的Length大于实际给定的Data，需要程序自行未尾补0，小于则末尾截断

每条指令一行，一个用例输入可以是多条指令混合，只有Read指令有输出。

每个用倒保证指令、参数格式正确，但不保证参数范围，需要程序照题目规格要求自行校验，参数不合法，则对应的指令无效。

每个用例保证需要存储的总数据量最大不超过16MB。一个用例最多不超过500条指令。

例如(3表示有3条指令)

3

Write 0x100 7 001122AA

Read 0x100 4

Clear

输出描述

采用字节流(2个16进制数表示一个Byte)，全大写

例如 001122AA

每条Read指令对应一行输出数据，如果指令给的参数不合法，对应的输出为空(不换行)。

样例

输入1

1
Read 0x100 4

输出1

00000000

说明

0x100地址空间未被写入数据，默认返回全0，一共4个字节

输入2

3
Write 0x100 8 00001122AABBCCDD
Read 0x100 12
Clear

输出2

00001122AABBCCDD00000000

说明

0x100地址，前8个字节被写入了有效数据00001122AABBCCDD，读取0x100地址12字节数据，后4个字节补齐默认数0，因此结果为00001122AABBCCDD00000000

题面描述

塔子哥正在研究虚拟化内存，并希望实现一个地址范围为32G的内存机制，支持数据的读写和清空操作。输入包括多个指令，格式为“Command Address Length Data”，其中Command可以是Read、Write或Clear，Address是64位无符号十六进制数，Length是64位无符号十进制数，Data是以字节流形式表示的十六进制数据。输出只针对Read指令，返回相应地址的数据，若参数不合法则不输出。示例输入包括Write、Read和Clear指令，程序需要根据指令处理内存数据，并确保符合题目要求。

思路：哈希表模拟

观察数据规模，存储的数据量不超过16MB，即为$2^{24}$，因此可以使用哈希表来存储

• 执行Clear操作时，清空哈希表即可
• 执行Write操作时，按位置写入每个字节
• 执行Read操作时，首先需要判断哈希表中是否存在，如果不存在，使用00代替，

每次执行Write和Read操作时，都需要判断输入的长度$len$是否在合法范围，$len$的合法范围为$0\le len \le 2^{34}$

代码流程说明

1. 输入处理：使用 input().split(",") 读取输入并将字符串转换为整数列表，表示每本书的满意值。

2. 排序：对书籍的满意值进行升序排序，以便优先阅读满意值低的书籍，最大化最终的快乐值。

3. 计算初始快乐值：

   • 使用一个循环遍历所有书籍，计算当所有书籍都被阅读时的总快乐值，并存储在变量 ret 中。这里使用了 (i + 1) 来表示书籍的阅读顺序对快乐值的影响。

4. 尝试舍弃书籍：

   • 使用一个循环，依次舍弃最前面的书籍。
   • 在每次舍弃书籍后，计算剩余书籍的快乐值并更新 ret，确保其保持为最大值。

5. 输出结果：最后，打印出计算得到的最大快乐值。

代码的优化建议

• 避免频繁的 pop(0) 操作：pop(0) 会导致列表的元素重排，时间复杂度为 O(n)，可以考虑使用索引来处理已舍弃的书籍，避免每次都修改列表。
• 更简洁的计算：可以通过累计的方式来更新快乐值，而不是每次重新计算，可以提高效率。

时间复杂度

$O(nlogn)$

代码

C++

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

// 使用哈希表存储地址和对应的数据
unordered_map<unsigned long long, string> m;

int main() {
    int n; // 指令数量
    cin >> n; // 输入指令的数量
    
    for (int i = 0; i < n; i++) {
        string cmd, data; // cmd为命令，data为数据
        unsigned long long address, length; // address为地址，length为长度
        cin >> cmd; // 读取命令
        
        if (cmd == "Write") {
            // 处理Write命令
            cin >> hex >> address >> dec >> length; // 读取地址（十六进制）和长度（十进制）
            cin >> data; // 读取数据（十六进制字符串）
            
            // 如果提供的数据长度小于指定长度，补零
            if (data.size() < length * 2) {
                string s(length * 2 - data.size(), '0'); // 生成补零字符串
                data += s; // 在data后添加补零
            }
            // 将数据写入对应地址
            m[address] = data;
        } else if (cmd == "Read") {
            // 处理Read命令
            cin >> hex >> address >> dec >> length; // 读取地址和长度
            
            // 判断地址是否存在
            if (m.find(address) != m.end()) {
                string data = m[address]; // 从哈希表中获取数据
                // 如果请求的长度大于存储的数据长度，进行补零
                if (length * 2 > data.size()) {
                    data += string(length * 2 - data.size(), '0'); // 追加补零
                } else {
                    // 截取到指定长度
                    data = data.substr(0, length * 2);
                }
                cout << data << endl; // 输出读取的数据
            } else {
                // 如果地址不存在，返回全0
                cout << string(length * 2, '0') << endl; // 返回补零
            }
        } else if (cmd == "Clear") {
            // 处理Clear命令
            m.clear(); // 清空哈希表
        }
    }
}

python代码

import sys
from collections import defaultdict

# 主要的处理函数
def solution(lines):
    n = len(lines)  # 获取输入行数
    rec = defaultdict(str)  # 使用defaultdict来存储地址到数据的映射，默认值为空字符串

    # 遍历每一行指令
    for line in lines:
        strs = line.split()  # 将每行指令按空格分割成字符串列表
        
        if strs[0] == 'Clear':
            # 如果指令是Clear，清空记录
            rec = defaultdict(str)  # 重新初始化defaultdict
            
        elif strs[0] == 'Write':
            # 如果指令是Write，处理写入操作
            add = strs[1]  # 获取地址
            if len(add) > 66:  # 如果地址长度超过66字符，跳过该指令
                continue
            
            length = int(strs[2])  # 获取写入的长度
            if length > 16 * 1024 * 1024:  # 如果长度超过16MB，跳过该指令
                continue
            
            data = strs[3]  # 获取要写入的数据
            if len(data) > length * 2:  # 如果数据长度大于指定长度
                data = data[:length * 2]  # 截取数据至指定长度
            
            rec[add] = data  # 将数据写入到对应的地址
            
        elif strs[0] == 'Read':
            # 如果指令是Read，处理读取操作
            add = strs[1]  # 获取地址
            if len(add) > 66:  # 如果地址长度超过66字符，跳过该指令
                continue
            
            length = int(strs[2])  # 获取读取的长度
            data = rec[add]  # 从记录中获取对应地址的数据
            
            if len(data) > length * 2:  # 如果获取的数据长度超过读取长度
                print(data[:length * 2])  # 输出截取的结果
            else:
                # 如果获取的数据长度小于读取长度，输出数据并补零
                print(data + ''.join(['0' for _ in range(length * 2 - len(data))]))  # 输出补零的结果

# 主函数
def main():
    n = int(input())  # 读取指令的数量
    lines = []  # 创建一个空列表来存储输入行
    for _ in range(n):
        lines.append(input())  # 逐行读取指令并添加到列表中
    
    solution(lines)  # 调用处理函数

# 执行主函数
main()

Java代码

import java.util.Arrays; // 导入Arrays类用于数组操作
import java.util.Scanner; // 导入Scanner类用于输入
import java.util.stream.IntStream; // 导入IntStream类用于流操作

public class Main {

    @SuppressWarnings({ "resource" }) // SuppressWarnings用于抑制警告
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建Scanner对象，用于读取输入
        String[] strs = sc.nextLine().split(","); // 读取一行输入并按逗号分割成字符串数组
        int[] arr = Arrays.stream(strs).mapToInt(Integer::parseInt).toArray(); // 将字符串数组转换为整数数组
        Arrays.sort(arr); // 对整数数组进行排序
        int[] sum = new int[arr.length]; // 创建一个数组用于存储从当前索引到末尾的和
        int res = 0; // 初始化结果变量
        
        // 遍历数组，计算从当前索引到末尾的和
        for (int i = 0; i < arr.length; i++) {
            // 计算从索引i到末尾的和，并存储在sum[i]
            sum[i] = IntStream.of(Arrays.copyOfRange(arr, i, arr.length)).sum();
            // 如果当前和大于0，累加到结果
            if (sum[i] > 0) {
                res = res + sum[i]; // 更新结果
            }
        }
        // 输出最终结果
        System.out.println(res);
    }
}