題意：
帕維爾有一些木棒，他們的長度分別為2的i次方（i>=0&&i<=n-1）給你他們的數量，盡可能用這些木棒組成最多的三角形。
思路：
眾所周知，三角形三邊滿足：a+b>c因此此題只有如下兩種情況才能組成三角形。
1.兩根長木棒和一根短木棒（第一類型）
2.三根同長的木棒（第二類型）
接著我們看如何組成才能保證答案最大。
當這根木棒的數量x=2時（假設存在比這根木棒小的木棒，x>=2）
只能組成一個第一類型的三角形。
x=3時，可以組成一個第一類型的三角形，或是一個第二類型的三角形。
x>3時可以組成n/3個第二類型的三角形，或是n/2個第一類型的三角形。明顯看出n/2>n/3。因此先選第一類型的三角形為最優解。

最后寫代碼的時候再注意一下比當前木棍短的木棍的數量。
?當時犯了一個很愚蠢的錯誤，認為不斷從a [ i ] a[i]a[i]中取走3到不能取是最優的，然后對3取模再求剩余匹配，產生這種想法很可能是被以往題目誤導了，后來想想，a = 4 , 4 , 4 a={4,4,4}a=4,4,4就輕松當反例了。

AC代碼：

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<string> #include<queue> #include<map> #include<stack> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define max 2000ll ans[300005];int main() {ll n;while (cin >> n){for (int i = 0; i < n; ++i)cin >> ans[i];ll count = 0,rem=0;for (int i = 0; i <n; ++i){int tow_s = min(ans[i] / 2, rem); //最多能構造類型一的數量rem -= tow_s; //因為每構造一個類型一就要用去前邊剩余的棍子count += tow_s; //答案加上類型一的數量ans[i] -= tow_s * 2; //因為每一個類型一需要用到的2個棍子count += ans[i] / 3; //構造類型三的三角形數量rem += ans[i] % 3; //剩余的加入}cout << count << endl;}return 0;} 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的Pavel and Triangles(贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

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