蓝桥杯算法提高VIP-盾神与积木游戏 （C++代码）

解题思路:

正好学到银行家算法这里，就想着用银行家算法的安全性判断的方式解决，结果超时，因为算法是Ｏ(n^2)的。问了地表最强召唤兽后突然醒悟。
原来只要排个序就行了，按照还需要的积木数从小到大排序，然后遍历所有作业，如果在某一次遍历中发现当前资源数不能满足某一个作业的需求，就退出，输出NO。

注意事项:

参考代码:

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

#define N 3

using namespace std;

class Job
{
private:
    int request;
    int allocated;
    int need;
public:
    Job(int r,int a):request(r),allocated(a){ need = request > allocated ? request - allocated : 0; }
    Job() { }
    int finish();
    int getNeed() { return need; }
    friend bool cmp(Job a,Job b);
};

int  Job::finish()
{
    int ret = allocated;
    request = need = allocated = 0;
    return ret;
}

bool cmp(Job a,Job b)
{
    return a.need < b.need;
}

vector<Job> jobArr;

int main()
{
    int m = 0;
    cin >> m;
    while(m--)
    {
        int n = 0;
        bool ans = true;
        cin >> n;
        jobArr.clear();
        for(int i = 0;i < n;i++)
        {
            int a = 0,r = 0;
            cin >> a >> r;
            jobArr.push_back(Job(r,a));
        }
        sort(jobArr.begin(),jobArr.end(),cmp);

        int srcSum = 0;
        for(vector<Job>::iterator it = jobArr.begin();it < jobArr.end();it++)
        {
            if(srcSum < it->getNeed())
            {
                ans = false;
                break;
            }
            else
                srcSum += it->finish();
        }
        if(ans)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

参考银行家算法（超时）：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <memory.h>
#define N 10000
using namespace std;
int request[N];
int allocated[N];
int need[N];
int sum;
int getReadyJob(int n)
{
int maxAllocated = 0;
int index = -1;
for (int i = 0; i < n; i++)
{
if (sum >= need[i] && request[i] > 0)
{
if (maxAllocated < allocated[i])
{
maxAllocated = allocated[i];
index = i;
}
}
}
return index;
}
void refreshNeed(int n)
{
for (int i = 0; i < n; i++)
if (request[i])
need[i] = request[i] > allocated[i] ? (request[i] - allocated[i]) : 0;
}
void finishJob(int i)
{
sum += allocated[i];
request[i] = 0;
allocated[i] = 0;
need[i] = 0;
}
bool solve(int n)
{
bool ans = true;
refreshNeed(n);
for (int time = 1; time <= n; time++)
{
int j;
if ((j = getReadyJob(n)) >= 0)
{
finishJob(j);
refreshNeed(n);
}
else
{
ans = false;
break;
}
}
return ans;
}
int main(int argc, char** argv)
{
int m = 0;
cin >> m;
while (m--)
{
int n = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> allocated[i];
cin >> request[i];
}
if (solve(n))
cout << "YES" << endl;
else
cout << "NO" << endl;
memset(allocated, 0x00, sizeof(allocated));
memset(request, 0x00, sizeof(request));
memset(need, 0x00, sizeof(need));
sum = 0;
}
return 0;
}