HDU 2474

この問題の鍵はデータ量が大きすぎて、普通の銀行家のアルゴリズムを使うと、最悪の場合、時間の複雑度はO(N*N*M)で、明らかにタイムアウトします.正しい解法は,各リソースを別々に考慮し,M個のキューを確立することである.プロセスは、各リソースに対する需要数を小さいものから大きいものまでキューに格納します.これにより、キューヘッダのプロセスを毎回チェックするだけで済みます.ソート時間複雑度O(M*N*logN)、各プロセスは最大M回まで、時間複雑度はO(N*M*M)である.
杭電のデータが弱いので、このアルゴリズムは効果が現れません...

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <memory.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iostream>
#include <sstream>

using namespace std;

int allo[3][50005], reqs[3][50005], avai[3], indx[3];
pair<int, int> queu[3][50005];
bool flag[3][50005];
int n, m;

int main() {
    int i, j, k, cunt;
    bool sign;
    while (scanf("%d %d", &n, &m) != EOF) {
        for (i = 0; i < m; i++)
            for (j = 0; j < n; j++)
                scanf("%d", &allo[i][j]);
        for (i = 0; i < m; i++)
            for (j = 0; j < n; j++) {
                scanf("%d", &reqs[i][j]);
                queu[i][j].first = reqs[i][j];
                queu[i][j].second = j;
            }
        for (i = 0; i < m; i++)
            scanf("%d", &avai[i]);
        for (i = 0; i < m; i++)
            sort(queu[i], queu[i] + n);
        sign = true;
        cunt = 0;
        memset(indx, 0, sizeof(indx));
        memset(flag, 0, sizeof(flag));
        while (sign) {
            sign = false;
            for (i = 0; i < m; i++) {
                for (j = indx[i]; j < n; j++) {
                    if (queu[i][j].first > avai[i])
                        break;
                    flag[i][queu[i][j].second] = true;
                    for (k = 0; k < m; k++) {
                        if (!flag[k][queu[i][j].second])
                            break;
                    }
                    if (k == m) {
                        sign = true;
                        cunt++;
                        for (k = 0; k < m; k++) {
                            avai[k] += allo[k][queu[i][j].second];
                            if (avai[k] > 1000000000)
                                avai[k] = 1000000000;
                        }
                    }
                }
                indx[i] = j;
            }
        }
        if (cunt == n) puts("Yes");
        else puts("No");
    }
    return 0;
}