正文之前

貌似我找到的那個(gè)題目網(wǎng)站更新了一波最新的題目。不過(guò)201709 只有1、2 題，所以先做了吧（其實(shí)是我自己對(duì)能不能做出第三題 持懷疑態(tài)度！）寶寶心里苦?。。?！??！！

正文

• 問(wèn)題描述
  　　小明帶著N元錢去買醬油。醬油10塊錢一瓶，商家進(jìn)行促銷，每買3瓶送1瓶，或者每買5瓶送2瓶。請(qǐng)問(wèn)小明最多可以得到多少瓶醬油。

• 輸入格式
  　　輸入的第一行包含一個(gè)整數(shù)N，表示小明可用于買醬油的錢數(shù)。N是10的整數(shù)倍，N不超過(guò)300。

• 輸出格式
  　　輸出一個(gè)整數(shù)，表示小明最多可以得到多少瓶醬油。

• 樣例輸入
  40

• 樣例輸出
  5

• 樣例說(shuō)明
  　　把40元分成30元和10元，分別買3瓶和1瓶，其中3瓶送1瓶，共得到5瓶。

• 樣例輸入
  80

• 樣例輸出
  11

• 樣例說(shuō)明
  　　把80元分成30元和50元，分別買3瓶和5瓶，其中3瓶送1瓶，5瓶送2瓶，共得到11瓶。

這個(gè)題目我也不好說(shuō)啥~~ 反正看懂了就看懂了~~ ，沒(méi)看懂再去練練吧~

#include<iostream>
using namespace std;

int main()
{
    int a,b,c,d;
    cin>>d;
    a=d/50;
    b=(d-50*a)/30;
    c=(d-50*a-30*b)/10;
    cout<<7*a+4*b+c<<endl;
}

Last login: Wed Nov 29 15:46:43 on ttys000
HustWolf:~ zhangzhaobo$ /Users/zhangzhaobo/program/C++/CCF_2017_09_1 ; exit;
80
11
logout
Saving session...
...copying shared history...
...saving history...truncating history files...
...completed.

[進(jìn)程已完成]

• 問(wèn)題描述
  　　有一個(gè)學(xué)校的老師共用N個(gè)教室，按照規(guī)定，所有的鑰匙都必須放在公共鑰匙盒里，老師不能帶鑰匙回家。每次老師上課前，都從公共鑰匙盒里找到自己上課的教室的鑰匙去開(kāi)門，上完課后，再將鑰匙放回到鑰匙盒中。
  　　鑰匙盒一共有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。

這個(gè)題目的內(nèi)核在于，你要把每次的取鑰匙和放鑰匙當(dāng)做兩個(gè)時(shí)間分別存入你的事件庫(kù)里面，也就是說(shuō)，每次取鑰匙，算是一個(gè)事件，有一個(gè)作用對(duì)象，有一個(gè)作用時(shí)間;每次放鑰匙，也算是一個(gè)事件，有一個(gè)作用對(duì)象，有一個(gè)作用時(shí)間。這樣，我們自定義一個(gè)時(shí)間結(jié)構(gòu)體或者說(shuō)是對(duì)象，主要的難點(diǎn)在于因?yàn)榧尤肓?algorithm標(biāo)準(zhǔn)庫(kù)的sort函數(shù)，所以要自頂一個(gè)operator< 運(yùn)算符，這樣sort的時(shí)候可以根據(jù)自定義的運(yùn)算符進(jìn)行排序，因?yàn)橐M的是事件流。所以以時(shí)間為刻度，把每次事件放到相應(yīng)的時(shí)間點(diǎn)， 并且先放后取，這樣才能細(xì)水長(zhǎng)流。當(dāng)然，因?yàn)樽詈蟾鶕?jù)鉤子的順序輸出鑰匙的順序，?? 所以我們還需要定義一個(gè)對(duì)象 gouzi 。當(dāng)然，我這里直接用vector解決這個(gè)問(wèn)題，也是可以的！然后我們可以對(duì)排序后的事件庫(kù)進(jìn)行按序讀取，這樣就跳過(guò)了空白的時(shí)間點(diǎn)，當(dāng)然，另一種思路是做時(shí)間長(zhǎng)度次遍歷，每次遍歷里面再遍歷整個(gè)事件庫(kù)，找到對(duì)應(yīng)事件發(fā)生的事情，至于時(shí)間復(fù)雜度？？呵呵??~

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

struct ACTION
{
    int key;
    int use_way;
    int time;
    ACTION(int a,int b,int c):key(a),use_way(b),time(c){}
    bool operator< (const ACTION&a) const
    {
        if(time<a.time)
            return true;
        else if(time==a.time && use_way<a.use_way)
            return true;
        else if(time==a.time && use_way==a.use_way && key<a.key)
            return true;
        else return false;
    }
};
int main()
{
    int N,K;
    cin>>N>>K;
    vector<int> gouzi;
    for(int i=0;i<=N;++i)
        gouzi.push_back(i);
    vector<ACTION> action;
    for(int i=0;i<K;++i)
    {
        int w,s,c;
        cin>>w>>s>>c;
        action.push_back(ACTION(w,1,s));
        action.push_back(ACTION(w,0,s+c));
    }
    sort(action.begin(),action.end());
    for(int i=0;i<action.size();++i)
    {
        if(action[i].use_way==0)
        {
            for(int j=0;j<N+1;++j)
            {
                if(gouzi[j]== -1)
                {
                    gouzi[j]=action[i].key;
                    break;
                }
            }
        }
        else
        {
            for(int j=0;j<N+1;++j)
            {
                if(gouzi[j]==action[i].key)
                {
                    gouzi[j]=-1;
                    break;
                }
            }
        }
    }
    for(int i=1;i<=N;++i)
    {
        cout<<gouzi[i]<<" ";
    }
    cout<<endl;
    return 0;
}

運(yùn)行結(jié)果如下：

Last login: Sat Dec  2 21:53:39 on ttys000
HustWolf:~ zhangzhaobo$ /Users/zhangzhaobo/program/C++/CCF_2017_09_2 ; exit;
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 
logout
Saving session...
...copying shared history...
...saving history...truncating history files...
...completed.

[進(jìn)程已完成]

正文之后

寶寶心里苦?。。?！ ?? ?? 今天CCF的試題庫(kù)我才發(fā)現(xiàn)正常運(yùn)行了??！ 所以去樂(lè)滋滋的把自己做的題目測(cè)試一下??！結(jié)果！！GG，祈禱明天能有200分。也算是達(dá)到了計(jì)算機(jī)考研生的免復(fù)試線，不然就太丟人了??！

還有?。?！最過(guò)分的是： 我不知道??！ 還可以帶紙質(zhì)資料。 那我還背并查集 Dijkstra BFS DFS 字典序 歐拉路徑 鄰接矩陣 鄰接表 這些干嘛喲?。。∥秩瞻。。?！