【实习机试真题】-hw0330-第一题

题目：芯片资源限制 一个业务芯片的容量为10G，可支持两种不同的业务类型A、B。芯片的约束如下： A业务容量为2.5G，一个芯片上最多可配置4路业务； B业务容量为10G，一个芯片上最多可配置1路业务； 由于业务容量限制，配置了A业务后，该芯片就不能配置B业务； 不能跨芯片占用资源，即业务只能配置在一块芯片上，不能占用一块芯片的容量，再占用另外芯片容量； 为了保证使用最少的芯片资源，业务配置时，按芯片编号从小到大顺序一次配置，并优先使用已经占用的芯片。 由于业务容量最小为2.5G，以最小业务容量为单位，一个芯片可以划分为4个资源区，将资源区依次编号为1，2，3，4. 一块板卡有M块芯片，用户进行一系列业务配置后，请输出最后一个业务对应的芯片编号和芯片资源ID，如果没有可用资源返回0 0

输入： 板卡芯片数量M，芯片范围为1~32 用户业务配置数量N，数量为1~128 用户业务配置，业务配置间以空格分隔

输出： 芯片编号 芯片资源ID

样例1： 输入：5 6 A B A B A A 输出：1 4 样例2： 输入：2 3 B A B 输出：0 0

解题思路：模拟方法

按顺序部署N个用户业务（A或者B） 对于每个当前需要部署在板卡上的业务，按顺序遍历板卡上的每个芯片，并找到第一个可以部署的芯片，并部署在芯片上 所以需要对每个芯片的状态（是否已经部署业务）进行记录 还要在部署新的业务时，对所部署芯片的状态进行更新

需要建立一些容器来记录 ：

vector<bool> isFull(M, false);

//这个状态优先级最高，记录每个芯片当前是否是满的，满的情况只有两种：一种是4个A，一种是一个B

vector<int> num_bus(M, 0);

//这个状态优先级较低，记录每个芯片当前有几个业务。

//为啥说状态优先级低？如果第j个芯片的isFull[j]=true,就不管有几个业务了。

vector<bool> isAllocate(N, 0);

//记录每个业务是否成功被部署在芯片上；

下面是模拟的具体过程：

对N个业务按顺序进行遍历： 按顺序对M个芯片进行遍历，找到后跳出循环 当前芯片是满的，直接进行下一次循环 当前芯片不满 当前芯片的业务数不为0（此情况说明部署了<4个的A业务） 如果当前业务是B，进行下一次循环； 如果当前业务是A，进行部署，更新状态(num_bus++，如果num_bus=4,is_full=true)，退出循环； 当前芯片的业务数为0： 如果当前业务是B，进行部署，更新状态(is_full=true,num_bus更不更新无所谓了)，退出循环； 如果当前业务是A，进行部署，更新状态，退出循环

代码：

#include<iostream>
#include<vector>
using namespace std;
vector<int> solution(int M, int N, vector<char>& b) {
	// A:2.5
	// B:10
	vector<int> res = { 0, 0 };
	vector<bool> isFull(M, false);
	vector<int> Num_bus(M, 0);
	vector<bool> isAllocate(N, false);
	for (int i = 0; i < b.size(); ++i) {
		for (int j = 0; j < isFull.size(); ++j) {
			if (!isFull[j]) {  //是不满的
				if (Num_bus[j] != 0) {
					if (b[i] == B) {
						continue;
					}
					else {  //b[i] = A, Num_bus[j]++;
						Num_bus[j] ++;
						if (Num_bus[j] == 4) isFull[j] = true;
						isAllocate[i] = true;
						res[0] = j + 1;
						res[1] = Num_bus[j];
						break;
					}
				}
				else {  //Num_bus[j] = 0
					if (b[i] == B) {
						isFull[j] = true;
						Num_bus[j] = 1;
						isAllocate[i] = true;
						res[0] = j + 1;
						res[1] = Num_bus[j];
						break;
					}
					else {
						Num_bus[j] ++;
						isAllocate[i] = true;
						res[0] = j + 1;
						res[1] = Num_bus[j];
						break;
					}
				}
			}
		}
		if (!isAllocate[i]) return { 0, 0 };
	}
	return res;
}
int main() {
	int M;
	cin >> M;
	int N;
	cin >> N;
	vector<char> business(N);
	for (int i = 0; i < N; ++i) {
		cin >> business[i];
	}
	vector<int> res = solution(M, N, business);
	cout << res[0] << endl;
	cout << res[1] << endl;

}

结果：