PAT Basic 1065. 單身狗(25)(C語言實(shí)現(xiàn))

我的PAT系列文章更新重心已移至Github护锤,歡迎來看PAT題解的小伙伴請(qǐng)到Github Pages瀏覽最新內(nèi)容摔笤。此處文章目前已更新至與Github Pages同步步淹。歡迎star我的repo磕秤。

題目

“單身狗”是中文對(duì)于單身人士的一種愛稱筑累。本題請(qǐng)你從上萬人的大型派對(duì)中找出落單的客人,以便給予特殊關(guān)愛。

輸入格式:

輸入第一行給出一個(gè)正整數(shù) N( \le 50 000)互亮,是已知夫妻/伴侶的對(duì)數(shù)犁享;隨后 N 行,每行給出一對(duì)夫妻/伴侶——為方便起見胳挎,每人對(duì)應(yīng)一個(gè) ID
號(hào)饼疙,為 5 位數(shù)字(從 00000 到 99999)溺森,ID 間以空格分隔慕爬;之后給出一個(gè)正整數(shù) M( \le 10
000),為參加派對(duì)的總?cè)藬?shù)屏积;隨后一行給出這 M 位客人的 ID医窿,以空格分隔。題目保證無人重婚或腳踩兩條船炊林。

輸出格式:

首先第一行輸出落單客人的總?cè)藬?shù)姥卢;隨后第二行按 ID 遞增順序列出落單的客人。ID 間用 1 個(gè)空格分隔渣聚,行的首尾不得有多余空格独榴。

輸入樣例:

3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333

輸出樣例:

5
10000 23333 44444 55555 88888

思路

很有......單身狗歧視的一道題! ! ! (為什么分值最多的題要提及這么沉重的話題 (;′⌒`))

設(shè)計(jì)了一個(gè)方法, 只用一個(gè)int[100000]數(shù)組來解決問題:

  1. 一對(duì)夫婦ID保存在數(shù)組中兩個(gè)元素中, 形成雙向的映射, 這個(gè)基本所有人都是這么做的
  2. 逐一讀取來客ID
  • 如果ID有對(duì)應(yīng)值, 說明有配偶, 數(shù)組相應(yīng)位置標(biāo)記"已簽到"(使用宏定義定義為一個(gè)負(fù)值)
  • 如果ID沒有對(duì)應(yīng)值, 說明是單身狗, 數(shù)組相應(yīng)位置標(biāo)記"落單"(另一個(gè)宏定義)
  1. 遍歷數(shù)組, 不管值為"已簽到"和"落單"的. 如果一個(gè)ID對(duì)應(yīng)有非負(fù)值(即合法ID值,說明他/她是有配偶的), 進(jìn)一步如果這個(gè)值對(duì)應(yīng)值是"已簽到"奕枝,說明ID沒有來, 而他/她的配偶來了(對(duì)照上面操作不難理解). ID這個(gè)人算是"落單",標(biāo)記上
  2. 再遍歷一次, 值為"落單"的輸出即可

看了一下網(wǎng)上其他人的做法, 很多都用了高級(jí)語言的功能, 如Python的dict, C++的set和map(只用C的表示完全不知道用C++的在做什么╮(╯▽╰)╭)棺榔。當(dāng)然還有時(shí)間復(fù)雜度O(N*M)的.
我的方法沒有使用任何的高級(jí)數(shù)據(jù)結(jié)構(gòu)/算法, 寫出的代碼也挺簡潔的, 只需要遍歷兩邊數(shù)組, 運(yùn)行時(shí)間不到10ms, 還有點(diǎn)小驕傲呢_

代碼

最新代碼@github,歡迎交流

#include <stdio.h>

#define BLANK -1
#define SIGNED -2
#define SINGLE -3

int main()
{
    int couple[100000], count = 0, N, M, ID1, ID2;
    for(int i = 0; i < 100000; i++)
        couple[i] = BLANK;

    /* Read 'couple-list', every pair of 'index' and 'value' are a couple. */
    scanf("%d", &N);
    for(int i = 0; i < N; i++)
    {
        scanf("%d %d", &ID1, &ID2);
        couple[ID1] = ID2;
        couple[ID2] = ID1;
    }

    scanf("%d", &M);
    for(int i = 0; i < M; i++)          /* Read guest list. */
    {
        scanf("%d", &ID1);
        if(couple[ID1] >= 0)                /* If one has a mate */
            couple[ID1] = SIGNED;           /*   set SIGNED */
        else                                /* Else: not in the 'couple-list' */
            couple[ID1] = SINGLE, count++;  /*   set SINGLE */
    }

    /* If couple[ID] is >= 0 (but not signed) but couple[couple[ID]] == SIGNED
     * (signed in), this means 'ID' didn't come but his/her mate did.
     * So his/her mate is alone in the party, set to SINGLE. */
    for(int i = 0; i < 100000; i++)
        if(couple[i] >= 0 && couple[couple[i]] == SIGNED)
            couple[couple[i]] = SINGLE, count++;

    /* Those whose value is SINGLE is either a bachelor or came alone */
    printf("%d\n", count);
    for(int i = 0; i < 100000; i++)
        if(couple[i] == SINGLE)
            printf("%05d%c", i, --count ? ' ' : '\0');

    return 0;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末隘道,一起剝皮案震驚了整個(gè)濱河市症歇,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌谭梗,老刑警劉巖忘晤,帶你破解...
    沈念sama閱讀 211,561評(píng)論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異激捏,居然都是意外死亡设塔,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,218評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門远舅,熙熙樓的掌柜王于貴愁眉苦臉地迎上來壹置,“玉大人,你說我怎么就攤上這事表谊〕ぃ” “怎么了?”我有些...
    開封第一講書人閱讀 157,162評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵爆办,是天一觀的道長难咕。 經(jīng)常有香客問我,道長,這世上最難降的妖魔是什么余佃? 我笑而不...
    開封第一講書人閱讀 56,470評(píng)論 1 283
  • 正文 為了忘掉前任暮刃,我火速辦了婚禮,結(jié)果婚禮上爆土,老公的妹妹穿的比我還像新娘椭懊。我一直安慰自己,他們只是感情好步势,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,550評(píng)論 6 385
  • 文/花漫 我一把揭開白布氧猬。 她就那樣靜靜地躺著,像睡著了一般坏瘩。 火紅的嫁衣襯著肌膚如雪盅抚。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,806評(píng)論 1 290
  • 那天,我揣著相機(jī)與錄音,去河邊找鬼竟坛。 笑死,一個(gè)胖子當(dāng)著我的面吹牛丰包,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播壤巷,決...
    沈念sama閱讀 38,951評(píng)論 3 407
  • 文/蒼蘭香墨 我猛地睜開眼邑彪,長吁一口氣:“原來是場噩夢(mèng)啊……” “哼!你這毒婦竟也來了隙笆?” 一聲冷哼從身側(cè)響起锌蓄,我...
    開封第一講書人閱讀 37,712評(píng)論 0 266
  • 序言:老撾萬榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎撑柔,沒想到半個(gè)月后瘸爽,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,166評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡铅忿,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,510評(píng)論 2 327
  • 正文 我和宋清朗相戀三年剪决,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片檀训。...
    茶點(diǎn)故事閱讀 38,643評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡柑潦,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出峻凫,到底是詐尸還是另有隱情渗鬼,我是刑警寧澤,帶...
    沈念sama閱讀 34,306評(píng)論 4 330
  • 正文 年R本政府宣布荧琼,位于F島的核電站譬胎,受9級(jí)特大地震影響差牛,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜堰乔,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,930評(píng)論 3 313
  • 文/蒙蒙 一偏化、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧镐侯,春花似錦侦讨、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,745評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至袜瞬,卻和暖如春怜俐,著一層夾襖步出監(jiān)牢的瞬間身堡,已是汗流浹背邓尤。 一陣腳步聲響...
    開封第一講書人閱讀 31,983評(píng)論 1 266
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留贴谎,地道東北人汞扎。 一個(gè)月前我還...
    沈念sama閱讀 46,351評(píng)論 2 360
  • 正文 我出身青樓,卻偏偏與公主長得像擅这,于是被迫代替她去往敵國和親澈魄。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,509評(píng)論 2 348

推薦閱讀更多精彩內(nèi)容

  • 傳送門 https://pintia.cn/problem-sets/994805260223102976/pro...
    Rush的博客閱讀 1,282評(píng)論 0 0
  • Spring Cloud為開發(fā)人員提供了快速構(gòu)建分布式系統(tǒng)中一些常見模式的工具(例如配置管理仲翎,服務(wù)發(fā)現(xiàn)痹扇,斷路器,智...
    卡卡羅2017閱讀 134,633評(píng)論 18 139
  • 第5章 引用類型(返回首頁) 本章內(nèi)容 使用對(duì)象 創(chuàng)建并操作數(shù)組 理解基本的JavaScript類型 使用基本類型...
    大學(xué)一百閱讀 3,216評(píng)論 0 4
  • 我的PAT系列文章更新重心已移至Github溯香,歡迎來看PAT題解的小伙伴請(qǐng)到Github Pages瀏覽最新內(nèi)容鲫构。...
    OliverLew閱讀 1,270評(píng)論 1 1
  • 姓名: 王中偉 公司:大發(fā)化纖有限公司 【日精進(jìn)打卡第81天】 【知~學(xué)習(xí)】 《六項(xiàng)精進(jìn)》背誦1遍...
    三車間王中偉閱讀 132評(píng)論 0 0