#P3213. 最优资源分配(200分)
-
1000ms
Tried: 47
Accepted: 30
Difficulty: 3
所属公司 :
华为od
最优资源分配(200分)
题面描述
某块业务芯片最小容量单位为 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