[数据结构与算法]CCF 公共钥匙盒（满分代码 + 解题思路）201709-2

题目描述

解题思路

• 数据范围不大，根据题目思路暴力模拟取钥匙和还钥匙的过程
• 第一，根据时间来做事，所以可以用时间来处理事务，时间越小越先处理
• 第二，如果一个时刻，有借有还，先还再借，如果有多个还，先还小的，再还大的
• 为了方便，我们可以将借和还分开存在两个不同的数组，然后将数组根据时间进行排序，根据时间来触发
  
  

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, k;
int w, s, c;

struct pk //pick取钥匙的结构体数组
{
    int num;
    int time; //开始借的时间

    bool operator< (const pk & t)const //根据时间从小到大排序
    {
        return time < t.time;
    }
}p[N];

struct bk //back还钥匙的结构体数组
{
    int num;
    int time; //还钥匙的时间

    bool operator< (const bk & t)const
    {
        if (time == t.time) return num < t.num; //如果同一个时间多个老师还钥匙，编号小的钥匙先还
        else return time < t.time;
    }
}b[N];

int a[N];

int main()
{
    cin >> n >> k;

    for (int i = 1; i <= n; i ++)
    {
        a[i] = i;
    }

    for (int i = 0; i < k; i ++)
    {
        cin >> w >> s >> c;
        p[i] = {w, s};
        b[i] = {w, s + c};
    }

    sort(p, p + k);
    sort(b, b + k);

    int pcnt = 0, bcnt = 0;
    for (int t = 0; t <= 10110; t ++)
    {
        while (b[bcnt].time == t) //先处理t时刻还钥匙的所有事件
        {
            for (int i = 1; i <= n; i ++)
            {
                if (a[i] == -1)
                {
                    a[i] = b[bcnt].num;
                    break;
                }
            }
            bcnt ++;
        }

        while (p[pcnt].time == t) //再处理t时刻借钥匙的所有事件
        {
            for (int i = 1; i <= n; i ++)
            {
                if (a[i] == p[pcnt].num)
                {
                    a[i] = -1;
                    break;
                }
            }
            pcnt ++;
        }
        if (pcnt == k && bcnt == k) break; //所有事件均处理完
    }

    for (int i = 1; i <= n; i ++)
    {
        cout << a[i] << " ";
    }
    return 0;
}