立志用更少的代碼做更高效的表達

---

Pat乙級最優化代碼+題解+分析匯總——>傳送門

---

給定一段一段的繩子，你需要把它們串成一條繩。每次串連的時候，是把兩段繩子對折，再如下圖所示套接在一起。這樣得到的繩子又被當成是另一段繩子，可以再次對折去跟另一段繩子串連。每次串連后，原來兩段繩子的長度就會減半。

給定 N 段繩子的長度，你需要找出它們能串成的繩子的最大長度。

輸入格式：
每個輸入包含 1 個測試用例。每個測試用例第 1 行給出正整數 N (2≤N≤10^?4 )；第 2 行給出 N 個正整數，即原始繩段的長度，數字間以空格分隔。所有整數都不超過10^?4。

輸出格式：
在一行中輸出能夠串成的繩子的最大長度。結果向下取整，即取為不超過最大長度的最近整數。

輸入樣例：
8
10 15 12 3 4 13 1 15
輸出樣例：
14

---

題意解析：

輸入：
3
15 15 1

如果15和15先連起來， 再和1連，那么計算過程是： ((15+15)/2 + 1 ) / 2 = 8

如果15和1先連起來，在和15連，那么計算過程是： ( (15+1)/2 + 15) / 2 = 11.5

也就是說： 我們需要找到一個計算順序，使最后得到的繩子最長

規律顯而易見， 從小到大逐步將繩子串起來，得到的結果最大。

---

代碼

#include<bits/stdc++.h> using namespace std; int a[10010]; int main() {priority_queue<double, vector<double>, greater<double> > q;int n; cin >> n;for(int i = 0; i < n; i++) {double x; cin >> x; q.push(x);}while(1) {if(q.size() == 1) break;double x1 = q.top(); q.pop();double x2 = q.top(); q.pop();q.push((x1+x2)/2.0);}cout << (int)(q.top()) << '\n'; return 0; }

---

耗時

---

每日一句

要活成兩種樣子，發光和不發光。不發光的時候，都是在為發光做準備~

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的【最详细解析】1070 结绳 (25分)_18行代码AC的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。