试题 I: 负载均衡

时间限制: 1.0s 内存限制: 256.0MB 本题总分：25 分

【问题描述】

有 n 台计算机，第 i 台计算机的运算能力为 vi。
有一系列的任务被指派到各个计算机上，第 i 个任务在 ai 时刻分配，指定
计算机编号为 bi ，耗时为 ci 且算力消耗为 di 。如果此任务成功分配，将立刻
开始运行，期间持续占用 bi 号计算机 di 的算力，持续 ci 秒。
对于每次任务分配，如果计算机剩余的运算能力不足则输出 −1，并取消这
次分配，否则输出分配完这个任务后这台计算机的剩余运算能力。

【输入格式】

输入的第一行包含两个整数 n, m，分别表示计算机数目和要分配的任务数。
第二行包含 n 个整数 v1, v2, · · · vn，分别表示每个计算机的运算能力。
接下来 m 行每行 4 个整数 ai, bi, ci, di，意义如上所述。数据保证 ai 严格递增，即 ai < ai+1。

【输出格式】

输出 m 行，每行包含一个数，对应每次任务分配的结果。

【样例输入】

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

【样例输出】

2
-1
-1
1
-1
0

【样例说明】

时刻 1，第 1 个任务被分配到第 1 台计算机，耗时为 5 ，这个任务时刻 6
会结束，占用计算机 1 的算力 3。
时刻 2，第 2 个任务需要的算力不足，所以分配失败了。
时刻 3，第 1 个计算机仍然正在计算第 1 个任务，剩余算力不足 3，所以
失败。
时刻 4，第 1 个计算机仍然正在计算第 1 个任务，但剩余算力足够，分配
后剩余算力 1。
时刻 5，第 1 个计算机仍然正在计算第 1, 4 个任务，剩余算力不足 4，失
败。
时刻 6，第 1 个计算机仍然正在计算第 4 个任务，剩余算力足够，且恰好
用完。

【评测用例规模与约定】

对于 20% 的评测用例，n, m ≤ 200。
对于 40% 的评测用例，n, m ≤ 2000。
对于所有评测用例，1 ≤ n, m ≤ 200000，1 ≤ ai, ci, di, vi ≤ 109，1 ≤ bi ≤ n。

题解

#include <iostream>
#include <vector>
using namespace std;

//单个pc状态的数组
struct pc {
    int num;
    int all_power;
    int now_power;
    vector< pair<int, int> > status;//endtime power
};

typedef pc pcc;

//单个任务的情况
struct task {
    int time;
    int tar_pc;
    int use_time;
    int use_power;
};

typedef task taskc;

//两个数组
vector<pcc> pcs;
vector<taskc> tasks;

void output_pcs() {
    for (int i = 0; i < pcs.size(); i++)
    {
        cout << pcs[i].num << " " << pcs[i].all_power << " " << pcs[i].now_power << " " << pcs[i].status.size() << endl;
        if (pcs[i].status.size() > 0) {
            for (int ii = 0; ii < pcs[i].status.size(); ii++)
            {
                cout << pcs[i].status[ii].first << "-" << pcs[i].status[ii].second << endl;
            }
        }
    }
    cout << endl;
}
void output_tasks() {
    for (int i = 0; i < tasks.size(); i++)
    {
        cout << tasks[i].time << " " << tasks[i].tar_pc << " " << tasks[i].use_time << " " << tasks[i].use_power << endl;
    }
    cout << endl;
}

int main2() {
    vector<int> s;
    s.push_back(1);
    s.push_back(2);
    s.push_back(3);
    s.push_back(4);
    vector<int>::iterator  begin;
    for (begin = s.begin(); begin != s.end(); begin++) {
        if ((*begin) == 3) {
            begin = s.erase(begin);
        }
        cout << (*begin) << endl;
    }
    //for (int i = 0; i < s.size(); i++)
    //{
    //  if (i == 3) {
    //      s.erase(;
    //  }
    //}
    return 0;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int temp_power;
        cin >> temp_power;
        pcc temp;
        temp.num = i;
        temp.all_power = temp_power;
        temp.now_power = 0;
        pcs.push_back(temp);
    }
    //cout << endl;

    //output_pcs();

    for (int i = 0; i < m; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        taskc temp;
        temp.time = a;
        temp.tar_pc = b;
        temp.use_time = c;
        temp.use_power = d;
        tasks.push_back(temp);
    }
    //cout << endl;
    //output_tasks();

    int end_over_time =tasks[tasks.size() - 1].time;
    //cout << "任务最终时：" << end_over_time << endl;

    //以时间为轴，更新每个任务和每个pc的状态
    for (int i = 1; i <= end_over_time; i++)
    {
        //cout << "-----------------" << endl;
        //cout << "第" << i << " 秒"<< endl;
        //改变pc状态
        //cout << "开始检查"<< endl;
        //output_pcs();
        for (int pi = 0; pi < n; pi++)
        {
            if (pcs[pi].now_power == 0) {
                //cout << "没有用过的电脑不检查" << pi + 1 << endl;
                continue;//没有用过的电脑不检查
            }
            //cout<<"开始检查电脑"<< pi + 1 << endl;
            if (pcs[pi].status.size() > 0) {
                //cout << "第" << pi << "台电脑任务列表大于0--" << pcs[pi].status.size() << endl;
                vector< pair<int, int> >::iterator begin;
                for (begin = pcs[pi].status.begin(); begin != pcs[pi].status.end(); begin++) {//处理里面的循环 //endtime power
                    //cout << "是否超过删除时间：删除真假" << ((*begin).first<i)<<"-end_time:"<< ((*begin).first) <<"-now_time:"<< (i) << endl;
                    //return 0;
                    if (i > (*begin).first) {//如果里面运行任务的时间小于当前时间，就要删除改任务
                        pcs[pi].now_power -= (*begin).second;//更新now_power的状态
                        begin = pcs[pi].status.erase(begin);
                    }
                }
            }
        }
        //cout << "输出改变后的电脑状态" << endl;
        //output_pcs();


        //接受新任务 || 这里循环怕他出现 1234 8 10 这种情况
        for (int si = 0; si < m; si++)
        {
            if (tasks[si].time == i) {//表示该任务这个时刻要执行
                //cout << "执行第" << si << "个任务" << endl;
                //cout << "目标计算机" << tasks[si].tar_pc << endl;
                int res_power = pcs[tasks[si].tar_pc - 1].all_power - pcs[tasks[si].tar_pc - 1].now_power - tasks[si].use_power;
                //cout << "假如删除后，第" << tasks[si].tar_pc << "台电脑算力情况：" << res_power <<endl;
                if (res_power >= 0) {//表示当前电脑算力有剩余的
                    //更新状态
                    pcs[tasks[si].tar_pc - 1].now_power = pcs[tasks[si].tar_pc - 1].all_power - res_power;
                    pcs[tasks[si].tar_pc - 1].status.push_back(make_pair(tasks[si].use_time+i-1, tasks[si].use_power));
                    //输出剩余算力
                    //cout <<"------答案可以----"<< res_power <<endl;
                    cout <<res_power <<endl;
                }else {
                    //cout<<"------答案不行----"<< -1 << endl;
                    cout<< -1 << endl;
                }
                break;
            }
        }

        //cout <<i << "秒后pc状态" << endl;
        //output_pcs();
        //cout << "============================================================" << endl;
    }

    return 0;
}