问题描述

进程调度是操作系统设计中非常重要的问题。每个进程都需要一定的资源才能运行，这些资源在进程结束时都会被释放。不同的资源分配策略会对系统的运行效率产生很大的影响，甚至可能导致死锁。

某系统中现有$n$个进程和m种资源。每个进程开始时得到部分资源，但不足以使得进程顺利执行，还需要得到其它资源才能执行。现已知该系统中各类可用资源的总量，给定的若干进程及其资源分配和需求情况，请指出这些进程是否能够顺利执行？

输入

输入数据有若干组，每组包括四部分：

第一部分为一行，含两个正整数 $n(n\le 50000)$ 和 $m(m\le 100)$ ，分别表示进程数量和资源的种类。

第二部分为随后的 $m$ 行。每行含有 $n$ 个整数，为各个进程得到的资源数。

第三部分也是 $m$ 行，紧随第二部分之后。每行包含 $n$ 个整数，代表进 程还需要的资源数。

第四部分为一行，紧随第三部分之后。该行包含 $m$ 个整数，为系统中当前各类可用资源的数量。

所有的整数值小于或等于 109109 。

输出

输出中只包含只Yes或No。

如果所有进程均能顺利完成，输出Yes, 否则输出No。

示例输入

4 3
1 6 2 0
0 1 1 0
0 2 1 2
2 0 1 4
2 0 0 2
2 1 3 0
0 1 1
4 3
2 5 2 0
0 1 1 0
1 1 1 2
1 1 1 4
2 0 0 2
1 2 3 0
0 1 1 

示例输出

Yes
No

解答

#include 
#include 
#define MAXN 50000
#define MAXM 100
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) != EOF) {
        int allocation[n][MAXM], need[n][MAXM], work[MAXM], finish[n];
        int available[MAXM];
        // 初始化allocation数组
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                scanf("%d", &allocation[j][i]);
            }
        }
        // 初始化need数组
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                scanf("%d", &need[j][i]);
            }
        }
        // 初始化available数组
        for (int i = 0; i < m; ++i) {
            scanf("%d", &available[i]);
            work[i] = available[i];
        }
        // 初始化finish数组
        for (int i = 0; i < n; ++i) {
            finish[i] = 0;
        }
        // 寻找可以完成的进程
        int allFinish = 1;
        do {
            allFinish = 1;
            for (int i = 0; i < n; ++i) {
                if (!finish[i]) { // 如果进程未完成
                    int canAllocate = 1;
                    for (int j = 0; j < m; ++j) { if (need[i][j] > work[j]) {
                            canAllocate = 0;
                            break;
                        }
                    }
                    if (canAllocate) { // 如果有足够的资源分配给进程
                        for (int j = 0; j < m; ++j) {
                            work[j] += allocation[i][j]; // 回收资源
                        }
                        finish[i] = 1;
                        allFinish = 0;
                    }
                }
            }
        } while (!allFinish);
        // 检查是否有未完成的进程
        int canComplete = 1;
        for (int i = 0; i < n; ++i) {
            if (!finish[i]) {
                canComplete = 0;
                break;
            }
        }
        if (canComplete) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}