題目鏈接:http://codeforces.com/problemset/problem/712/C

題意:

　　給你兩個值 a 和 b (a > b), 代表這里有兩個等邊三角形, 邊長分別為 a 和 b, 你可以對邊長為 a 的三角形進行變換, 每次變化你可以選擇一條邊, 并為其重新指定一個長度, 當然變換完成后還能組成一個三角形.問最少經過多少次變換可以把等邊三角形的三邊長度從 a 變換到 b.

思路:

　　題目中的意思時從大的三角形變換到小的三角形,這里可以換一種方式,即 “最少經過多少次變換可以把邊長從 b 變到 a”, 可以想到, 這里需要做的就是讓三條邊在變化范圍中盡可能的接近 a. 即對于邊長 (b_a, b_b, b_c), 第一條邊長的長度變化范圍為 b_a < b_b + b_c , 如果這里 b_b + b_c?<= a, 那么為了讓 b_a 更接近 a, 就可以讓 b_a 取 b_b + b_c? - 1,如果 b_b + b_c?< a, 則 b_a 直接取 a 就好了; 然后對于第二條邊 b_b 做出同樣的變換,然后已知迭代下去, 直到 b_a = b_b? = b_c = a, 結束變換就好了.

代碼:

1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long LL; 5 6 const int MAXN = 100000; 7 int st, ed, ans = 0; 8 9 void solv(int a, int b, int c) { 10 if(a == b && a == c && a == st) return ; 11 ans++; 12 if(ans % 3 == 1) st < b + c ? a = st : a = b + c - 1;//讓第一條邊盡可能接近 st 13 else if(ans % 3 == 2) st < a + c ? b = st : b = a + c - 1; 14 else st < a + b ? c = st : c = a + b - 1; 15 solv(a, b, c); 16 } 17 18 int main() { 19 ios_base::sync_with_stdio(); cin.tie(); 20 cin >> st >> ed; 21 solv(ed, ed, ed); 22 cout << ans << endl; 23 return 0; 24 }

　

轉載于:https://www.cnblogs.com/Ash-ly/p/5861440.html

總結

以上是生活随笔為你收集整理的Codeforces 712C. Memory and De-Evolution的全部內容，希望文章能夠幫你解決所遇到的問題。

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