cs101暑假班summer unit3最小最大

1、CS101 信奧算法資料的固定請(qǐng)每次課前自行將資料到電腦快快編程地址請(qǐng)登陸提交作業(yè)htt/s/13VZqsD4jDUdKelF6wocF3wsetmultiset數(shù)據(jù)容器樹(shù)RB-tree數(shù)據(jù)結(jié)構(gòu)：set和multiset的底層實(shí)現(xiàn)都是樹(shù)易錯(cuò)點(diǎn)大部分情況，建議使用multiset元素應(yīng)該重復(fù)出現(xiàn)時(shí)，不能使用set，應(yīng)該使用multiset數(shù)據(jù)容器：multiset和set multiset 和 set 可較快完成對(duì)一組數(shù)據(jù)的常規(guī)操作，包括： 刪除 查找 計(jì)數(shù) 去重 排序 multiset 允許元素重復(fù)出現(xiàn)set 保證元素唯一性，不允許元素重復(fù) 找最小/最大begin(),end(),rbegin

2、(),rend()end()反向迭代器reverse_iterator0123rend()rbegin()迭代器iteratorbegin()迭代器 和 反向迭代器找最小值 begin() *(s.begin() 找第二小元素: 方法1s.erase(s.begin()*(s.begin()刪除最小元素找第二小元素: 方法2begin()it+*it迭代器往后移找第二小元素: 易錯(cuò)點(diǎn)會(huì)刪除所有等于最小值元素找最大值:方法1 rbegin() 反向迭代器 *(s.rbegin() 找最大值:方法2 end() 迭代器前移 end()it-找第二大元素: 方法1end()it-*it迭代器前移找第

3、二大元素: 方法2迭代器前移只刪除一個(gè)最大元素找第二大元素: 方法3rbegin()it+*it反向迭代器移動(dòng)找第二大元素: 易錯(cuò)點(diǎn)1會(huì)刪除所有等于最大值元素找第二大元素: 易錯(cuò)點(diǎn)2s.erase(s.rbegin()會(huì)報(bào)錯(cuò)erase()參數(shù)不可用反向迭代器找第二大元素: 易錯(cuò)點(diǎn)3刪除元素后迭代器 會(huì)失效例題：樣例輸出2樣例輸出4樣例輸入230 30樣例輸入530 10 20 200 210小組賽如火如荼地開(kāi)展，今天共有n場(chǎng)比賽，每場(chǎng)比賽i都有一個(gè)開(kāi)始時(shí)間ti（以分鐘為 ），如果兩場(chǎng)比賽的開(kāi)始時(shí)間相差大于等于200分鐘，那么這兩場(chǎng)球賽可以安排在一個(gè)足球場(chǎng)進(jìn)行。否則，由于時(shí)間間隔太短容易引起 ，

4、必須將兩場(chǎng)球賽分開(kāi)到不同球場(chǎng)。輸入第一行為n，第二行為n個(gè)正整數(shù)分別代表每場(chǎng)比賽的開(kāi)賽時(shí)間。輸出至少需要幾個(gè)足球場(chǎng)。0=n=16例題：如果最早空閑的球場(chǎng)不能舉辦這場(chǎng)比賽，就新增一個(gè)足球場(chǎng)否則就在最早空閑球場(chǎng)舉辦這場(chǎng)比賽按照開(kāi)賽時(shí)間先后，依次查看每場(chǎng)比賽：定義一個(gè)multiset容器叫stadiums 存放現(xiàn)有足球場(chǎng)的當(dāng)前球賽的開(kāi)賽時(shí)間定義一個(gè)multiset容器叫g(shù)ames存放所有比賽的開(kāi)賽時(shí)間請(qǐng)嘗試翻譯每一句話請(qǐng)嘗試翻譯每一句話例題：數(shù)字合并樣例輸出15367樣例輸出8樣例輸入68 6 5 9 7 1樣例輸入31 2 3有n個(gè)正整數(shù)，現(xiàn)在進(jìn)行若干次操作：每次刪去2個(gè)數(shù)a和 b，然后加入1個(gè)數(shù)

5、a*b+1。反復(fù)操作直到只有一個(gè)數(shù)，求最小剩下幾？ （1=n=1000）數(shù)字合并每次找最大的兩個(gè)數(shù)字a和b合并。也就是從容器s中取出最大兩個(gè)數(shù)a和b，然后刪除最大的兩個(gè)數(shù)，再a*b+1貪心算法選數(shù)字，重復(fù)執(zhí)行：定義一個(gè)multiset容器叫s存放所有目前的數(shù)字例題：木條切割切割問(wèn)題轉(zhuǎn)換為合并問(wèn)題樣例輸出34樣例輸入38 8 5有一根長(zhǎng)木條能恰好被切割成n塊。這n塊的長(zhǎng)度是 L1,L2,L3,.,Ln。開(kāi)始時(shí)，木條總長(zhǎng)為(L1+L2+L3+.+Ln)。每次切斷一段木條時(shí)，費(fèi)用為這段木條的長(zhǎng)度。如果按照要求切割完成，最少需要多少費(fèi)用？1=n=100例題：木條切割每次找最小的兩個(gè)數(shù)字a和b合并。也就是從容器s中取出最小兩個(gè)數(shù)a和b，然后刪除最小的兩個(gè)數(shù)，再a+b貪心算法選長(zhǎng)度，重復(fù)執(zhí)行：定義一個(gè)multiset容器叫s存放所有目前的木條長(zhǎng)度切割問(wèn)題