Problem Description

試題編號(hào)： 201709-2
試題名稱： 公共鑰匙盒
時(shí)間限制： 1.0s
內(nèi)存限制： 256.0MB
問(wèn)題描述：
　　有一個(gè)學(xué)校的老師共用N個(gè)教室，按照規(guī)定，所有的鑰匙都必須放在公共鑰匙盒里，老師不能帶鑰匙回家。每次老師上課前，都從公共鑰匙盒里找到自己上課的教室的鑰匙去開(kāi)門(mén)，上完課后，再將鑰匙放回到鑰匙盒中。
　　鑰匙盒一共有N個(gè)掛鉤，從左到右排成一排，用來(lái)掛N個(gè)教室的鑰匙。一串鑰匙沒(méi)有固定的懸掛位置，但鑰匙上有標(biāo)識(shí)，所以老師們不會(huì)弄混鑰匙。
　　每次取鑰匙的時(shí)候，老師們都會(huì)找到自己所需要的鑰匙將其取走，而不會(huì)移動(dòng)其他鑰匙。每次還鑰匙的時(shí)候，還鑰匙的老師會(huì)找到最左邊的空的掛鉤，將鑰匙掛在這個(gè)掛鉤上。如果有多位老師還鑰匙，則他們按鑰匙編號(hào)從小到大的順序還。如果同一時(shí)刻既有老師還鑰匙又有老師取鑰匙，則老師們會(huì)先將鑰匙全還回去再取出。
　　今天開(kāi)始的時(shí)候鑰匙是按編號(hào)從小到大的順序放在鑰匙盒里的。有K位老師要上課，給出每位老師所需要的鑰匙、開(kāi)始上課的時(shí)間和上課的時(shí)長(zhǎng)，假設(shè)下課時(shí)間就是還鑰匙時(shí)間，請(qǐng)問(wèn)最終鑰匙盒里面鑰匙的順序是怎樣的？
輸入格式
　　輸入的第一行包含兩個(gè)整數(shù)N, K。
　　接下來(lái)K行，每行三個(gè)整數(shù)w, s, c，分別表示一位老師要使用的鑰匙編號(hào)、開(kāi)始上課的時(shí)間和上課的時(shí)長(zhǎng)。可能有多位老師使用同一把鑰匙，但是老師使用鑰匙的時(shí)間不會(huì)重疊。
　　保證輸入數(shù)據(jù)滿足輸入格式，你不用檢查數(shù)據(jù)合法性。
輸出格式
　　輸出一行，包含N個(gè)整數(shù)，相鄰整數(shù)間用一個(gè)空格分隔，依次表示每個(gè)掛鉤上掛的鑰匙編號(hào)。
樣例輸入
5 2
4 3 3
2 2 7
樣例輸出
1 4 3 2 5
樣例說(shuō)明
　　第一位老師從時(shí)刻3開(kāi)始使用4號(hào)教室的鑰匙，使用3單位時(shí)間，所以在時(shí)刻6還鑰匙。第二位老師從時(shí)刻2開(kāi)始使用鑰匙，使用7單位時(shí)間，所以在時(shí)刻9還鑰匙。
　　每個(gè)關(guān)鍵時(shí)刻后的鑰匙狀態(tài)如下（X表示空）：
　　時(shí)刻2后為1X345；
　　時(shí)刻3后為1X3X5；
　　時(shí)刻6后為143X5；
　　時(shí)刻9后為14325。
樣例輸入
5 7
1 1 14
3 3 12
1 15 12
2 7 20
3 18 12
4 21 19
5 30 9
樣例輸出
1 2 3 5 4
評(píng)測(cè)用例規(guī)模與約定
　　對(duì)于30%的評(píng)測(cè)用例，1 ≤ N, K ≤ 10, 1 ≤ w ≤ N, 1 ≤ s, c ≤ 30；
　　對(duì)于60%的評(píng)測(cè)用例，1 ≤ N, K ≤ 50，1 ≤ w ≤ N，1 ≤ s ≤ 300，1 ≤ c ≤ 50；
　　對(duì)于所有評(píng)測(cè)用例，1 ≤ N, K ≤ 1000，1 ≤ w ≤ N，1 ≤ s ≤ 10000，1 ≤ c ≤ 100。

Solution

注：因?yàn)橥粋€(gè)老師一定是先借鑰匙再還鑰匙，所以借與還不存在矛盾，將所有老師借鑰匙與還鑰匙按時(shí)間排序，并且同時(shí)有多個(gè)老師還鑰匙時(shí)按鑰匙編號(hào)順序排序，然后按序進(jìn)行借與還的操作。本題中使用結(jié)構(gòu)體，以及比較函數(shù)用sort進(jìn)行排序操作。最終結(jié)果只得70分，有待后續(xù)改進(jìn)。

Code

/*****************************************
Filename:   Main
Author:     cwhong
Date:       2018.07.06
Description:csp2017-09-2,公共鑰匙盒

******************************************/

#include<iostream>
#include<algorithm>

using namespace std;

int key[1001];

typedef struct Teacher
{
    // type 為0表示該老師是借，1則是還
    int type;
    // time 表示老師借或者還鑰匙的時(shí)間
    int time;
    // key 表示該鑰匙的編號(hào)
    int key;
}t;

t teacher[2002];

bool Compare(t a,t b)
{
    // return a.time < b.time;
    if (a.time < b.time)
    {
        // 首先按使用時(shí)間排序
        return a.time > b.time;
    }
    else if (a.time == b.time)
    {
        // 時(shí)間相同則還鑰匙在前
        if (a.type < b.type)
        {
            return true;
        }
        else if (a.type == 1 && b.type == 1)
        {
            // 同時(shí)有多把鑰匙要還則按鑰匙編號(hào)從小到大順序還
            return a.key > b.key;
        }

    }
}

void KeyFunction(int key_num,int teacher_num)
{
    int i,j,k;
    for (i=teacher_num*2;i>=1;i--)
    {
        if (teacher[i].type == 0)
        {
            for (j=1;j<=key_num;j++)
            {
                if (teacher[i].key == key[j])
                {
                    key[j] = 0;
                    break;
                }
            }
        }
        else if (teacher[i].type == 1)
        {
            for (j=1;j<=key_num;j++)
            {
                if (key[j] == 0)
                {
                    key[j] = teacher[i].key;
                    break;
                }
            }
        }
    }
}

main ()
{
    // 鑰匙數(shù)量，老師數(shù)量
    int key_num,teacher_num;
    cin>>key_num>>teacher_num;

    int i,j,k;
    for (i=1;i<=key_num;i++)
    {
        key[i] = i;
    }
    int a,b,c;
    for (i=1;i<=teacher_num;i++)
    {
        cin>>a>>b>>c;
        teacher[i*2 - 1].type = 0;
        teacher[i*2 - 1].time = b;
        teacher[i*2 - 1].key = a;
        teacher[i*2].type = 1;
        teacher[i*2].time = b+c;
        teacher[i*2].key = a;
    }

    // cout<<endl;
    // for (i=1;i<=teacher_num*2;i++)
    // {
    //  cout<<teacher[i].type<<" "<<teacher[i].time<<" "<<teacher[i].key<<endl;
    // }
    // cout<<endl;

    sort(teacher + 1,teacher + teacher_num*2 + 1,Compare);

    // for (i=1;i<=teacher_num*2;i++)
    // {
    //  cout<<teacher[i].type<<" "<<teacher[i].time<<" "<<teacher[i].key<<endl;
    // }
    // cout<<endl;
    KeyFunction(key_num,teacher_num);

    for (i=1;i<=key_num;i++)
    {
        cout<<key[i]<<" ";
    }
    cout<<endl;

    return 0;
}