有一台机器,上面有m个储存空间。然后有n个请求,第i个请求计算时需要占 R[i]个空间,储存计算结果则需要占据O[i]个空间(据O[i]个空间(其中O[i]

有一台机器,上面有m个储存空间。然后有n个请求,第i个请求计算时需要占 R[i]个空间,储存计算结果则需要占据O[i]个空间(据O[i]个空间(其中O[i]<R[i])。问怎么安排这n个请求的顺序,使得所有请求都能完成。你的算法也应该能够判断出无论如何都不能处理完的情况。

比方说,m=14,n=2,R[1]=10,O[1]=5,R[2]=8,O[2]=6。在这个例子中,我们可以先运行第一个任务,剩余9个单位的空间足够执行第二个任务;但如果先走第二个任务,第一个任务执行时空间就不够了,因为10>14-6。

//请求数
#define N 2
//存储空间
#define M 14

typedef struct request {
	int no;
	int r;
	int o;
} REQ;

void printReqs(REQ* reqs, int len) {
	for (int i = 0; i < len - 1; ++i) {
		cout << reqs[i].no << "->";
	}
	cout << reqs[len - 1].no << endl;
}

int cmp(const void* req1, const void* req2) {
	return (((const REQ*) req2)->r - ((const REQ*) req2)->o)
			- (((const REQ*) req1)->r - ((const REQ*) req1)->o);
}

//获取处理完所有请求所需的存储空间
int getAllOccupy(REQ* reqs, int len) {
	int sum = 0;
	for (int i = 0; i < len; ++i) {
		sum += reqs[i].o;
	}
	return sum;
}

bool arrangeDealRequest(REQ* reqs, int len) {
	if (!reqs || !len) {
		return false;
	}
	int occupy = getAllOccupy(reqs, len);

//必定不满足的情况: 处理完所有请求后所需空间小于指定空间
	if (M < occupy) {
		cout << "存储空间不足!!!";
		return false;

	} else {
		int curSpace = M;
		//按照R[i]-O[i]的值降序排序
		qsort(reqs, len, sizeof(REQ), cmp);
		for (int i = 0; i < len; ++i) {
			if (curSpace >= reqs[i].r) {
				curSpace -= reqs[i].o;
			} else {
				cout << "运行空间不足!!!";
				return false;
			}
		}
		return true;
	}
}
上一篇:laravel配置路由除了 / 都是404解决办法


下一篇:NOIP2017 D1T3 逛公园