题面描述

某块业务芯片最小容量单位为 1.25G，总容量为 M * 1.25G，对该芯片资源编号为 1，2，...，M。该芯片支持 3 种不同的配置，分别为 A、B、C。

• 配置 A：占用容量为 1.25 * 1 = 1.25G
• 配置 B：占用容量为 1.25 * 2 = 2.5G
• 配置 C：占用容量为 1.25 * 8 = 10G

某块板卡上集成了 N 块上述芯片，对芯片编号为 1，2，...，N，各个芯片之间彼此独立，不能跨芯片占用资源。

给定板卡上芯片数量 N、每块芯片容量 M、用户按次序配置后，请输出芯片资源占用情况，保证消耗的芯片数量最少。

资源分配规则：按照芯片编号从小到大分配所需资源，芯片上资源如果被占用标记为 1，没有被占用标记为 0。

用户配置序列：用户配置是按次序依次配置到芯片中，如果用户配置序列中某个配置超过了芯片总容量，丢弃该配置，继续遍历用户后续配置。

思路

模拟题，相当于是$A$芯片占一个格子，$B$芯片占两个格子，$C$芯片占八个格子，按照顺序遍历即可。

cpp

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

int main(){
    int M, N;
    string configs;
    // 读取输入
    cin >> M;
    cin >> N;
    cin >> configs;
    
    // 每个芯片的资源状态，初始化为0
    vector<string> chips(N, string(M, '0'));
    
    // 配置对应的资源单位
    unordered_map<char, int> config_map = {
        {'A', 1},
        {'B', 2},
        {'C', 8}
    };
    
    // 遍历每个配置
    for(char c : configs){
        // 获取该配置需要的资源单位
        if(config_map.find(c) == config_map.end()) continue; // 无效配置，跳过
        int required = config_map[c];
        bool allocated = false;
        
        // 遍历芯片
        for(int i=0; i<N; ++i){
            // 如果剩余资源不足，跳过
            int remaining = M - count(chips[i].begin(), chips[i].end(), '1');
            if(remaining < required) continue;
            
            // 在当前芯片中寻找连续的未占用资源块
            int start = -1;
            int count_free = 0;
            for(int j=0; j<M; ++j){
                if(chips[i][j] == '0'){
                    if(start == -1){
                        start = j;
                        count_free = 1;
                    }
                    else{
                        count_free++;
                    }
                    if(count_free == required){
                        break;
                    }
                }
                else{
                    start = -1;
                    count_free = 0;
                }
            }
            if(count_free == required){
                // 分配资源
                for(int k=start; k<start+required; ++k){
                    chips[i][k] = '1';
                }
                allocated = true;
                break; // 配置完成，处理下一个配置
            }
        }
        // 如果所有芯片都无法分配，丢弃该配置
    }
    
    // 输出每个芯片的资源占用情况
    for(auto &chip : chips){
        cout << chip << endl;
    }
    return 0;
}

python

# 读取输入
M = int(input())
N = int(input())
configs = input().strip()

# 初始化每个芯片的资源状态为'0'
chips = ['0' * M for _ in range(N)]

# 配置对应的资源单位
config_map = {
    'A': 1,
    'B': 2,
    'C': 8
}

for c in configs:
    if c not in config_map:
        continue  # 无效配置，跳过
    required = config_map[c]
    allocated = False
    
    for i in range(N):
        chip = chips[i]
        # 如果剩余资源不足，跳过
        if chip.count('1') + required > M:
            continue
        # 寻找连续的未占用资源块
        start = -1
        count_free = 0
        for j in range(M):
            if chip[j] == '0':
                if start == -1:
                    start = j
                    count_free = 1
                else:
                    count_free += 1
                if count_free == required:
                    break
            else:
                start = -1
                count_free = 0
        if count_free == required:
            # 分配资源
            chip = list(chip)
            for k in range(start, start + required):
                chip[k] = '1'
            chips[i] = ''.join(chip)
            allocated = True
            break  # 配置完成，处理下一个配置
    # 如果所有芯片都无法分配，丢弃该配置

# 输出每个芯片的资源占用情况
for chip in chips:
    print(chip)

java

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();
        String configs = sc.next();
        
        // 初始化每个芯片的资源状态为'0'
        StringBuilder[] chips = new StringBuilder[N];
        for(int i=0; i<N; i++) {
            chips[i] = new StringBuilder();
            for(int j=0; j<M; j++) chips[i].append('0');
        }
        
        // 配置对应的资源单位
        Map<Character, Integer> config_map = new HashMap<>();
        config_map.put('A', 1);
        config_map.put('B', 2);
        config_map.put('C', 8);
        
        // 遍历每个配置
        for(char c : configs.toCharArray()){
            if(!config_map.containsKey(c)) continue; // 无效配置，跳过
            int required = config_map.get(c);
            boolean allocated = false;
            
            // 遍历芯片
            for(int i=0; i<N; i++){
                StringBuilder chip = chips[i];
                // 计算剩余资源
                int used = 0;
                for(int k=0; k<M; k++) if(chip.charAt(k) == '1') used++;
                if(used + required > M) continue;
                
                // 寻找连续的未占用资源块
                int start = -1;
                int count_free = 0;
                for(int j=0; j<M; j++){
                    if(chip.charAt(j) == '0'){
                        if(start == -1){
                            start = j;
                            count_free = 1;
                        }
                        else{
                            count_free++;
                        }
                        if(count_free == required){
                            break;
                        }
                    }
                    else{
                        start = -1;
                        count_free = 0;
                    }
                }
                if(count_free == required){
                    // 分配资源
                    for(int k=start; k<start+required; k++) chip.setCharAt(k, '1');
                    allocated = true;
                    break; // 配置完成，处理下一个配置
                }
            }
            // 如果所有芯片都无法分配，丢弃该配置
        }
        
        // 输出每个芯片的资源占用情况
        for(int i=0; i<N; i++) System.out.println(chips[i].toString());
    }
}

题目内容

某块业务芯片最小容量单位为 1.25G，总容量为 M*1.25G，对该芯片资源编号为 $1，2，...，M$ 。该芯片支持 $3$ 种不同的配置，分别为 $A$、$B$、$C$ 。

• 配置 $A$：占用容量为 1.25 * 1 = 1.25G
• 配置 $B$ ：占用容量为 1.25 * 2 = 2.5G
• 配置 $C$ ：占用容量为 1.25 * 8 = 10G 某块板卡上集成了 $N$ 块上述芯片，对芯片编号为 $1 ，2，...，N$，各个芯片之间彼此独立，不能跨芯片占用资源。

给定板卡上芯片数量 $N$ 、每块芯片容量 $M$ 、用户按次序配置后，请输出芯片资源占用情况，保证消耗的芯片数量最少。

资源分配规则：按照芯片编号从小到大分配所需资源，芯片上资源如果被占用标记为 $1$ ，没有被占用标记为 $0$ 。

用户配置序列：用户配置是按次序依次配置到芯片中，如果用户配置序列种某个配置超过了芯片总容量，丢弃该配置，继续遍历用户后续配置。

输入描述

M：每块芯片容量为 M * 1.25G，取值范围为：$1$ ~ $256$

N：每块板卡包含芯片数量，取值范围为 $1$ ~ $32$

用户配置序列：例如 $ACABA$ ，长度不超过 $1000$

输出描述

板卡上每块芯片的占用情况

备注

用户配置是按次序依次配置到芯片中，如果用户配置序列种某个配置超过了芯片总容量，丢弃该配置，继续遍历用户后续配置。

样例1

输入

8
2
ACABA

输出

11111000
11111111

说明

用户第1个配置A：占用第1块芯片第1个资源，芯片占用情况为：

10000000

00000000

用户第2个配置C：第1块芯片剩余8.75G，配置C容量不够，只能占用第2块芯片，芯片占用情况为：

10000000

11111111

用户第3个配置A：第1块芯片剩余8.75G，还能继续配置，占用第1块芯片第2个资源，芯片占用情况为：

11000000

11111111

用户第4个配置B：第1块芯片剩余7.5G，还能继续配置，占用第1块芯片第3、4个资源，芯片占用情况为：

11110000

11111111

用户第5个配置A：第1块芯片剩余5G，还能继续配置，占用第1块芯片第5个资源，芯片占用情况为：

11111000

11111111

样例2

输入

8
2
ACBCB

输出

11111000
11111111

说明

用户第1个配置A：占用第1块芯片第1个资源，芯片占用情况为：

10000000

00000000

用户第2个配置C：第1块芯片剩余8.75G，配置C容量不够，只能占用第2块芯片，芯片占用情况为：

10000000

11111111

用户第3个配置B：第1块芯片剩余8.75G，还能继续配置，占用第1块芯片第2、3个资源，芯片占用情况为：

11100000

11111111

用户第4个配置C：芯片资源不够，丢弃配置，继续下一个配置，本次配置后芯片占用情况保持不变：

11100000

11111111

用户第5个配置B：第1块芯片剩余6.25G,还能继续配置，占用第1块芯片第4、5个资源，芯片占用情况为：

11111000

11111111