团队程序设计天梯赛-3.19排位赛总结
文章目錄
- 7-1 冠軍魔術 (10 分)
- 題目
- 知識點
- 代碼
- 7-2 單詞長度 (10 分)
- 題目
- 注意點
- 代碼
- 7-3 組個最小數 (15 分)
- 題目
- 知識點
- 代碼
- 7-4 檢查密碼 (15 分)
- 題目
- 思路
- 知識點
- 代碼
- 7-5 大炮打蚊子 (20 分)
- 題目
- 思路
- 代碼
- 7-6 出棧序列的合法性 (20 分)
- 題目描述
- 思路
- 代碼
- 7-7 社交網絡圖中結點的“重要性”計算 (25 分)
- 題目描述
- 思路
- 代碼
- 7-8 朋友圈 (25 分)
- 題目描述
- 思路
- 代碼
- 7-9 家譜處理 (25 分)
- 思路
- 代碼
- 7-10 狼人殺 (25 分)
- 題目描述
- 思路
- 代碼
- 7-11 串繩子 (25 分)
- 題目描述
- 思路
- 知識點
- 代碼一
- 代碼二（優先隊列）
7-1 冠軍魔術 (10 分)
題目
2018年FISM（世界魔術大會）近景總冠軍簡綸廷的表演中有一個情節：以桌面上一根帶子為界，當他將紙牌從帶子的一邊推到另一邊時，紙牌會變成硬幣；把硬幣推回另一邊會變成紙牌。
這里我們假設紙牌會變成等量的硬幣，而硬幣變成紙牌時，紙牌的數量會加倍。那么給定紙牌的初始數量，當他來回推了 N 次（來/回各算一次）后，手里拿的是紙牌還是硬幣？數量是多少？
輸入格式：
輸入在一行里給出兩個正整數，分別是紙牌的初始數量和魔術師推送的次數。這里假設初始狀態下魔術師手里全是紙牌。
輸出格式：
如果最后魔術師手里是紙牌，輸出 0 和紙牌數量；如果是硬幣，則輸出 1 和硬幣數量。數字間須有 1 個空格。題目保證結果數值不超出整型范圍（即 2
31
?1）。
輸入樣例 1：
3 7輸出樣例 1：
1 24輸入樣例 2：
8 4輸出樣例 2：
0 32知識點
找規律
代碼
#include<bits/stdc++.h> using namespace std; int main() {int num, n;cin >> num >> n;if(n%2==0) cout << "0 " << ?num*(int)pow(2, n/2);else cout << "1 " << ?num*(int)pow(2, (n-1)/2);return 0; }7-2 單詞長度 (10 分)
題目
你的程序要讀入一行文本，其中以空格分隔為若干個單詞，以.結束。你要輸出每個單詞的長度。這里的單詞與語言無關，可以包括各種符號，比如it’s算一個單詞，長度為4。注意，行中可能出現連續的空格；最后的.不計算在內。
輸入格式:
輸入在一行中給出一行文本，以.結束
輸出格式:
在一行中輸出這行文本對應的單詞的長度，每個長度之間以空格隔開，行末沒有最后的空格。
輸入樣例:
It's great to see you here.輸出樣例:
4 5 2 3 3 4注意點
注意會出現一個或多個空格后面接句號的特殊情況
注意若長度為0，不輸出0。比如：23 . , 輸出：2
代碼
#include<bits/stdc++.h> using namespace std; int main() {string s;int flag = 0;while(cin>>s) {if(s==".") break;if(flag) cout << " ";flag = 1;if(s.back()!='.') cout << s.length();else if(s.length()>1) cout << s.length()-1;}return 0; }7-3 組個最小數 (15 分)
題目
給定數字0-9各若干個。你可以以任意順序排列這些數字，但必須全部使用。目標是使得最后得到的數盡可能小（注意0不能做首位）。例如：給定兩個0，兩個1，三個5，一個8，我們得到的最小的數就是10015558。
現給定數字，請編寫程序輸出能夠組成的最小的數。
輸入格式：
輸入在一行中給出10個非負整數，順序表示我們擁有數字0、數字1、……數字9的個數。整數間用一個空格分隔。10個數字的總個數不超過50，且至少擁有1個非0的數字。
輸出格式：
在一行中輸出能夠組成的最小的數。
輸入樣例：
2 2 0 0 0 3 0 0 1 0輸出樣例：
10015558知識點
find_first_of()和find_last_of的使用：函數find_first_of() 查找在字符串中第1個出現的字符c，而函數find_last_of()查找最后一個出現的c。匹配的位置是返回值。如果沒有匹配發生，則函數返回-1.
find_first_of()和 find_last_of()
代碼
參考代碼(按順序輸入后交換）：
#include<iostream> #include<string> #include<algorithm> using namespace std; int main() {string s = "";int n;for(char i='0'; i<='9'; i++) {cin >> n;for(int j=0; j<n; j++) s += i;}int pos = s.find_last_of('0');if(pos!=-1) swap(s[0], s[pos+1]);cout << s;return 0; }我的代碼（排序后如果第一個為0則交換）：
#include <bits/stdc++.h> using namespace std; int main(){int a[10];vector<int> v;for(int i=0;i<10;i++){cin>>a[i];}for(int i=0;i<10;i++){while(a[i]--){v.push_back(i);}}sort(v.begin(),v.end());int pos;for(int i=0;i<v.size();i++){if(v[i]!=0){pos = i;break;}}if(v[0] == 0){int t = v[0];v[0] = v[pos];v[pos] = t;}for(int i=0;i<v.size();i++){cout<<v[i];} }7-4 檢查密碼 (15 分)
題目
本題要求你幫助某網站的用戶注冊模塊寫一個密碼合法性檢查的小功能。該網站要求用戶設置的密碼必須由不少于6個字符組成，并且只能有英文字母、數字和小數點 .，還必須既有字母也有數字。
輸入格式：
輸入第一行給出一個正整數 N（≤ 100），隨后 N 行，每行給出一個用戶設置的密碼，為不超過 80 個字符的非空字符串，以回車結束。
注意： 題目保證不存在只有小數點的輸入。
輸出格式：
對每個用戶的密碼，在一行中輸出系統反饋信息，分以下5種：
如果密碼合法，輸出Your password is wan mei.；
如果密碼太短，不論合法與否，都輸出Your password is tai duan le.；
如果密碼長度合法，但存在不合法字符，則輸出Your password is tai luan le.；
如果密碼長度合法，但只有字母沒有數字，則輸出Your password needs shu zi.；
如果密碼長度合法，但只有數字沒有字母，則輸出Your password needs zi mu.。
輸入樣例：
輸出樣例：
Your password is tai duan le. Your password needs shu zi. Your password needs zi mu. Your password is wan mei. Your password is tai luan le.思路
使用getline（）進行字符串的輸入
分別對不同情況進行處理即可
知識點
isalpha():判斷是否為字母
isdigit():判斷是否為數字（注意digit的拼寫！！！）
代碼
#include<iostream> #include<string> using namespace std; int main() {int n;cin >> n;getchar();string s;int flag, letter, num;for(int i=0; i<n; i++) {flag = 1;letter = num = 0;getline(cin, s);//含有空格的string字符串的讀入if(s.size()<6) {cout << "Your password is tai duan le.\n";continue;}for(int k=0; s[k]!='\0'; k++) {if(isalpha(s[k])) letter = 1;//含有字母else if(isdigit(s[k])) num = 1;//含有數字else if(s[k]!='.') { //只要碰到非法字符就退出flag = 0;break;}}if(flag==0) cout << "Your password is tai luan le.\n";else if(letter==0) cout << "Your password needs zi mu.\n";else if(num==0) cout << "Your password needs shu zi.\n";else cout << "Your password is wan mei.\n";} }7-5 大炮打蚊子 (20 分)
題目
現在，我們用大炮來打蚊子：蚊子分布在一個M×N格的二維平面上，每只蚊子占據一格。向該平面的任意位置發射炮彈，炮彈的殺傷范圍如下示意：
O OXOO其中，X為炮彈落點中心，O為緊靠中心的四個有殺傷力的格子范圍。若蚊子被炮彈命中（位于X格），一擊斃命，若僅被殺傷（位于O格），則損失一半的生命力。也就是說，一次命中或者兩次殺傷均可消滅蚊子。現在給出蚊子的分布情況以及連續k發炮彈的落點，給出每炮消滅的蚊子數。
輸入格式:
第一行為兩個不超過20的正整數M和N，中間空一格，表示二維平面有M行、N列。
接下來M行，每行有N個0或者#字符，其中#表示所在格子有蚊子。
接下來一行，包含一個不超過400的正整數k，表示發射炮彈的數量。
最后k行，每行包括一發炮彈的整數坐標x和y（0≤x<M，0≤y<N），之間用一個空格間隔。
輸出格式:
對應輸入的k發炮彈，輸出共有k行，第i行即第i發炮彈消滅的蚊子數。
輸入樣例:
5 6 00#00# 000### 00#000 000000 00#000 2 1 2 1 4輸出樣例:
0 2思路
將有蚊子的地方設為2，大炮剛好命中則-2，其周邊區域則-1，每次統計數量
代碼
#include<bits/stdc++.h> using namespace std; int a[21][21]; int fun(int x, int y) {//處理a[x][y]的蚊子int res = 0;if(a[x][y]==1) res = 1, a[x][y] = 0;else if(a[x][y]==2) a[x][y] = 1;return res; } int main() {int m, n;cin >> m >> n;char c;for(int i=0; i<m; i++)for(int j=0; j<n; j++) {cin >> c;if(c=='#') a[i][j] = 2;}int k;cin >> k;while(k--) {int x, y;cin >> x >> y;int res = 0;if(a[x][y]>0) res++, a[x][y] = 0;if(x>0) res += fun(x-1, y);if(x<m-1) res += fun(x+1, y);if(y>0) res += fun(x, y-1);if(y<n-1) res += fun(x, y+1);cout << res << endl;}return 0; }7-6 出棧序列的合法性 (20 分)
題目描述
給定一個最大容量為 M 的堆棧，將 N 個數字按 1, 2, 3, …, N 的順序入棧，允許按任何順序出棧，則哪些數字序列是不可能得到的？例如給定 M=5、N=7，則我們有可能得到{ 1, 2, 3, 4, 5, 6, 7 }，但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }。
輸入格式：
輸入第一行給出 3 個不超過 1000 的正整數：M（堆棧最大容量）、N（入棧元素個數）、K（待檢查的出棧序列個數）。最后 K 行，每行給出 N 個數字的出棧序列。所有同行數字以空格間隔。
輸出格式：
對每一行出棧序列，如果其的確是有可能得到的合法序列，就在一行中輸出YES，否則輸出NO。
輸入樣例：
5 7 5 1 2 3 4 5 6 7 3 2 1 7 5 6 4 7 6 5 4 3 2 1 5 6 4 3 7 2 1 1 7 6 5 4 3 2輸出樣例：
YES NO NO YES NO思路
數組a存放待比較的出棧序列，pos表示數組a當前要出棧的數的下標
st是容量為m的棧， 初始時1入棧。num順序取自1~n，初值為1
關鍵思想就是不斷出棧和不斷入棧，當既不能出棧也不能入棧，退出循環
循環后根據是否棧空判斷YES/NO
代碼
#include<bits/stdc++.h> using namespace std; int main() {int m, n, k;cin >> m >> n >> k;int a[1001];while(k--) {for(int i=1; i<=n; i++) cin >> a[i];stack<int> st;st.push(1);int num = 2, pos = 1;int flag = 1;while(flag) {flag = 0;while(!st.empty() && pos<=n && st.top()==a[pos]) {//滿足條件時不斷出棧st.pop();pos++;flag = 1;}while(st.size()<m && num<=n && num<=a[pos]) {//滿足條件時不斷入棧st.push(num);num++;flag = 1;}}if(st.empty()) cout << "YES\n";else cout << "NO\n";}return 0; }7-7 社交網絡圖中結點的“重要性”計算 (25 分)
題目描述
在社交網絡中，個人或單位（結點）之間通過某些關系（邊）聯系起來。他們受到這些關系的影響，這種影響可以理解為網絡中相互連接的結點之間蔓延的一種相互作用，可以增強也可以減弱。而結點根據其所處的位置不同，其在網絡中體現的重要性也不盡相同。
對于非連通圖，所有結點的緊密度中心性都是0。
給定一個無權的無向圖以及其中的一組結點，計算這組結點中每個結點的緊密度中心性。
輸入格式:
輸入第一行給出兩個正整數N和M，其中N（≤10
4
）是圖中結點個數，順便假設結點從1到N編號；M（≤10
5
）是邊的條數。隨后的M行中，每行給出一條邊的信息，即該邊連接的兩個結點編號，中間用空格分隔。最后一行給出需要計算緊密度中心性的這組結點的個數K（≤100）以及K個結點編號，用空格分隔。
輸出格式:
按照Cc(i)=x.xx的格式輸出K個給定結點的緊密度中心性，每個輸出占一行，結果保留到小數點后2位。
輸入樣例:
9 14 1 2 1 3 1 4 2 3 3 4 4 5 4 6 5 6 5 7 5 8 6 7 6 8 7 8 7 9 3 3 4 9輸出樣例:
Cc(3)=0.47 Cc(4)=0.62 Cc(9)=0.35思路
使用floyd計算任兩點的最短距離。
遍歷需要求的點到所有點的距離并相加（若遍歷圖中遇到非連通（距離為原來設立的MAX值）則可以終止了）
代碼
#include<bits/stdc++.h> using namespace std; #define MAX 100000//這個數值，只要是全大于任兩點的最大距離就行。 int n, m; int a[10001][10001]; void floyd() {for(int k=1; k<=n; k++)for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)a[i][j] = min(a[i][j], a[i][k]+a[k][j]); } int main() {cin >> n >> m;for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)a[i][j] = MAX;while(m--) {int x, y;cin >> x >> y;a[x][y] = a[y][x] = 1;}floyd(); // for(int i=1; i<=n; i++){ // for(int j=1; j<=n; j++){ // cout<<a[i][j]<<" "; // } // cout<<endl; // // }int k;cin >> k;int flag = 1;while(k--) {int x;cin >> x;double dis = 0;for(int i=1; i<=n && flag; i++) {if(i==x) continue;if(a[x][i]==MAX) flag = 0; //一旦flag為0，以后都不用算了，結果肯定都是0dis += a[x][i];}if(flag==0) printf("Cc(%d)=0.00\n", x);else printf("Cc(%d)=%.2f\n", x, (n-1)/dis);}return 0; }7-8 朋友圈 (25 分)
題目描述
某學校有N個學生，形成M個俱樂部。每個俱樂部里的學生有著一定相似的興趣愛好，形成一個朋友圈。一個學生可以同時屬于若干個不同的俱樂部。根據“我的朋友的朋友也是我的朋友”這個推論可以得出，如果A和B是朋友，且B和C是朋友，則A和C也是朋友。請編寫程序計算最大朋友圈中有多少人。
輸入格式:
輸入的第一行包含兩個正整數N（≤30000）和M（≤1000），分別代表學校的學生總數和俱樂部的個數。后面的M行每行按以下格式給出1個俱樂部的信息，其中學生從1~N編號：
第i個俱樂部的人數Mi（空格）學生1（空格）學生2 … 學生Mi
輸出格式:
輸出給出一個整數，表示在最大朋友圈中有多少人。
輸入樣例:
7 4 3 1 2 3 2 1 4 3 5 6 7 1 6輸出樣例:
4思路
使用并查集不斷合并有朋友關系的朋友，遍歷查找各個根節點的數量的最大值即為答案
還是并查集，但這次要加速，否則最后測試點超時
代碼
#include<bits/stdc++.h> using namespace std; int pre[30001]; int root(int x) { //平常的找根節點方法：（會慢一點） // while(x!=root[x]){ // x = root[x]; // } // return x;return x==pre[x]? x:pre[x]=root(pre[x]);//（可以加速！！！！！） } void un(int x, int y) {int px = root(x);int py = root(y);pre[px] = py; } int main() {int n, m;cin >> n >> m;for(int i=1; i<=n; i++) pre[i] = i;while(m--) {int k, x, y;cin >> k;cin >> x;while(--k) {cin >> y;un(x, y);x = y;}}map<int, int> mp;for(int i=1; i<=n; i++)mp[root(i)]++;int max = 0;for(auto x:mp) if(x.second>max) max = x.second;cout << max;return 0; }7-9 家譜處理 (25 分)
人類學研究對于家族很感興趣，于是研究人員搜集了一些家族的家譜進行研究。實驗中，使用計算機處理家譜。為了實現這個目的，研究人員將家譜轉換為文本文件。下面為家譜文本文件的實例：
JohnRobertFrankAndrewNancyDavid家譜文本文件中，每一行包含一個人的名字。第一行中的名字是這個家族最早的祖先。家譜僅包含最早祖先的后代，而他們的丈夫或妻子不出現在家譜中。每個人的子女比父母多縮進2個空格。以上述家譜文本文件為例，John這個家族最早的祖先，他有兩個子女Robert和Nancy，Robert有兩個子女Frank和Andrew，Nancy只有一個子女David。
在實驗中，研究人員還收集了家庭文件，并提取了家譜中有關兩個人關系的陳述語句。下面為家譜中關系的陳述語句實例：
John is the parent of Robert
Robert is a sibling of Nancy
David is a descendant of Robert
研究人員需要判斷每個陳述語句是真還是假，請編寫程序幫助研究人員判斷。
輸入格式:
輸入首先給出2個正整數N（2≤N≤100）和M（≤100），其中N為家譜中名字的數量，M為家譜中陳述語句的數量，輸入的每行不超過70個字符。
名字的字符串由不超過10個英文字母組成。在家譜中的第一行給出的名字前沒有縮進空格。家譜中的其他名字至少縮進2個空格，即他們是家譜中最早祖先（第一行給出的名字）的后代，且如果家譜中一個名字前縮進k個空格，則下一行中名字至多縮進k+2個空格。
在一個家譜中同樣的名字不會出現兩次，且家譜中沒有出現的名字不會出現在陳述語句中。每句陳述語句格式如下，其中X和Y為家譜中的不同名字：
X is a child of Y X is the parent of Y X is a sibling of Y X is a descendant of Y X is an ancestor of Y輸出格式:
對于測試用例中的每句陳述語句，在一行中輸出True，如果陳述為真，或False，如果陳述為假。
輸入樣例:
6 5 JohnRobertFrankAndrewNancyDavid Robert is a child of John Robert is an ancestor of Andrew Robert is a sibling of Nancy Nancy is the parent of Frank John is a descendant of Andrew輸出樣例:
True True True False False思路
難點在于：1. 使用什么數據結構來存儲家族關系。觀察問題，使用map! mp[孩子] = 老爸 最合適。
2. 如何讀入到map中，這里的難點是如何獲得當前讀入的名字的上一輩。這里可以使用棧。
棧里總是保存一層一層的父輩。因此棧的初值是最早祖先的父輩（設為“000”）。
再使用bk來記錄上一行輸入的空格數。因此bk的初值對應是最早祖先的父輩的縮進。由于最早祖先縮進
是0，因此其父輩的縮進是-2
若當前空格數k小于等于上一行的空格數bk，出棧(k+2-bk)/2次。這樣棧頂一定是當前的父輩
若當前空格數k大于上一行的空格數bk，那就說明棧頂本身就是當前的父輩。
找到父輩后，mp[當前] = 棧頂。然后當前入棧，為下次做準備。同時刷新bk的值
代碼
#include<bits/stdc++.h> using namespace std; int main() {int n, m;cin >> n >> m;getchar();stack<string> st;//用于存放一層一層的父輩序列st.push("000");//最早祖先的父輩設為 "000"int bk = -2;//上一次輸入的縮進空格數，初始值為-2（最早祖先縮進為0，他的父輩就是-2）map<string, string> mp;//mp[孩子] = 老爸while(n--) {string s;getline(cin, s);int k;for(k=0; s[k] && s[k]==' '; k++);//有多少個空格s = s.substr(k);//不取空格if(k <= bk)//當前空格數小于等于上次，說明上次一定不是當前的父輩for(int i=k; i<=bk; i+=2) st.pop();//把不是父輩的出棧mp[s] = st.top();//棧頂是當前的父輩st.push(s);//本次輸入入棧bk = k; //刷新上次空格數}string qs[100];while(m--) {int res = 0;for(int i=0; i<6; i++) cin >> qs[i];//利用空格作為cin的結束符string t;switch(qs[3][0])//利用第4個單詞的首字母來區分{case 'c':if(mp[qs[0]]==qs[5]) res = 1;break;//X is a child of Ycase 'p':if(mp[qs[5]]==qs[0]) res = 1;break;//X is the parent of Ycase 's':if(mp[qs[0]]==mp[qs[5]]) res = 1;break;//X is a sibling of Ycase 'd':t = qs[0];while(t!="000" && mp[t]!=qs[5]) t = mp[t];if(t!="000") res = 1;break;//X is a descendant of Ycase 'a':t = qs[5];while(t!="000" && mp[t]!=qs[0]) t = mp[t];if(t!="000") res = 1;break;//X is an ancestor of Y ????}if(res) cout << "True\n";else cout << "False\n";}return 0; }7-10 狼人殺 (25 分)
題目描述
以下文字摘自《靈機一動·好玩的數學》：“狼人殺”游戲分為狼人、好人兩大陣營。在一局“狼人殺”游戲中，1號玩家說：“2號是狼人”，2號玩家說：“3號是好人”，3號玩家說：“4號是狼人”，4號玩家說：“5號是好人”，5號玩家說：“4號是好人”。已知這5名玩家中有2人扮演狼人角色，有2人說的不是實話，有狼人撒謊但并不是所有狼人都在撒謊。扮演狼人角色的是哪兩號玩家？
本題是這個問題的升級版：已知 N 名玩家中有 M 人扮演狼人角色，有 L 人說的不是實話，有狼人撒謊但并不是所有狼人都在撒謊。要求你找出扮演狼人角色的是哪幾號玩家？
輸入格式:
輸入在第一行中給出三個正整數 N、M、L，其中 5 ≤ N ≤ 100，2 ≤ M，L < N。隨后 N 行，第 i 行給出第 i 號玩家說的話（1 ≤ i ≤ N），即一個玩家編號，用正號表示好人，負號表示狼人。
輸出格式:
如果有解，在一行中按遞減順序輸出 M 個狼人的編號，其間以空格分隔，行首尾不得有多余空格。如果解不唯一，則輸出最大序列解 —— 即對于兩個序列 A = { a[1], …, a[M] } 和 B = { b[1], …, b[M] }，若存在 0 ≤ k < M 使得 a[i]=b[i] （i ≤ k），且 a[k+1]>b[k+1]，則稱序列 A 大于序列 B。若無解則輸出 No Solution。
輸入樣例 1:
5 2 2 -2 +3 -4 +5 +4輸出樣例 1:
4 1輸入樣例 2:
6 2 3 -2 +3 -4 +5 +4 -3輸出樣例 2（解不唯一）:
6 4輸入樣例 3:
6 2 5 -2 +3 -4 +5 +4 +6輸出樣例 3:
No Solution思路
枚舉
編號從大到小枚舉每一套狼人方案，然后判斷這套方案是否滿足題目要求，是的話就搞掂
要獲得每一套狼人的編號方案，可使用dfs生成
代碼
#include<bits/stdc++.h> using namespace std; int n, m, l; int a[101], b[101]; bool judge(int a[], int b[]) { //判斷b數組中的m個狼人是否合理int tmp[101];//當前方案，1是好人，-1是狼人fill(tmp+1, tmp+n+1, 1);//好人for(int i=1; i<=m; i++) tmp[b[i]] = -1;//這些是狼人int cnt = 0;//根據假設情況，說假話的人數 ?int langcnt = 0;//說假話的狼人數量 ?for(int i=1; i<=n; i++) { //統計有多少人說假話int id = abs(a[i]);??if(a[i]*tmp[id]<0)//i說的話和假設的實際情況不一致，說明i說假話{cnt++;if(tmp[i]==-1) langcnt++;//i是狼人}}if(cnt==l && langcnt>0 && langcnt<m) return true;//說假話人數正確 且 有狼人 且 不 // 是全部狼人else return false; } bool dfs(int t) {//選出第t個狼人, 其編號寫入到b[t]串繩子：if(t==m+1) { //已選出了m個if(judge(a, b)) return true;//這m個狼人滿足要求} else {for(int i=b[t-1]-1; i>=1; i--) { //第t個狼人的候選人編號b[t] = i;if(dfs(t+1)) return true;}}return false; } int main() {cin >> n >> m >> l;for(int i=1; i<=n; i++) cin >> a[i];b[0] = n+1;if(!dfs(1)) cout << "No Solution";else {cout << b[1];for(int i=2; i<=m; i++) cout << " " << b[i];}return 0; }7-11 串繩子 (25 分)
題目描述
有若干條繩子需要成一條繩。把兩條繩子分別對折就可以套接在一起（見下圖）。這樣得到的繩子可以作為一條繩子與另一條進行串聯。每次串連后，原來兩段繩子的長度就會減半。
46293e57-aa0e-414b-b5c3-7c4b2d5201e2.jpg
給定 N 段繩子的長度，求它們能串成的繩子的最大長度。
輸入格式:
每個輸入包含 1 個測試用例。每個測試用例第 1 行給出正整數 N (2≤N≤10
4
)；第 2 行給出 N 個正整數，即原始繩段的長度，數字間以空格分隔。所有整數都不超過10
4
.
輸出格式:
在一行中輸出能夠串成的繩子的最大長度。結果向下取整，即取為不超過最大長度的最近整數。
輸入樣例:
8 10 15 12 3 4 13 1 15輸出樣例:
14思路
- 代碼一：直接用一個數組存，排序后用a[i] = (a[i]+a[i-1])/2不斷更新數組，a[n-1]即為答案
- 代碼二：使用小頂堆的優先隊列priority_queue<double,vector,greater > q;
知識點
優先隊列！！！
c++優先隊列(priority_queue)用法詳解
和隊列基本操作相同:
top 訪問隊頭元素
empty 隊列是否為空
size 返回隊列內元素個數
push 插入元素到隊尾 (并排序)
emplace 原地構造一個元素并插入隊列
pop 彈出隊頭元素
swap 交換內容
代碼一
#include<iostream> #include<string> #include<algorithm> using namespace std; int main() {int n;cin >> n;int a[10000];for(int i=0; i<n; i++) cin >> a[i];sort(a, a+n);for(int i=1; i<n; i++) a[i] = (a[i]+a[i-1])/2;cout << a[n-1];return 0; }代碼二（優先隊列）
#include <bits/stdc++.h> using namespace std; int main(){int n;cin>>n;priority_queue<double,vector<double>,greater<double> > q;for(int i=0;i<n;i++){double num;cin>>num;q.push(num);}while(q.size()>=2){double t1 = q.top();q.pop();double t2 = q.top();q.pop();double t3 = t1/2+t2/2;q.push(t3);}cout<<floor(q.top());}總結
以上是生活随笔為你收集整理的团队程序设计天梯赛-3.19排位赛总结的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 简易 Python 脚本查询嵊泗船票
- 下一篇： Nginx通过max_fails和fai