首页 > 代码库 > codeforces 712C C. Memory and De-Evolution(贪心)

codeforces 712C C. Memory and De-Evolution(贪心)

2024-08-13 22:45:09   221人阅读

题目链接：http://codeforces.com/problemset/problem/712/C

题目大意：

　　给连个值x,y (3 ≤ y < x ≤ 100 000), x，y都为等边三角形。从y等边三角形 每次修改一条边，且修改后的三个边还能组成一个三角形（两边之和大于第三边）。问修改几次能够得到x为边的等边三角形。

例如：

　　输入： 22 4　　输出： 6

　　技术分享

解题思路：

　　从y->x ，定义三个边y1=y2=y3=y,

　　每次修改一条边 y1=y2+y3-1(两边之和大于第三遍) 修改++ 如果y1>=x break;

　　修改一条边 y2=y1+y3-1 修改++ 如果y2>=x break;

　　修改一条边 y3=y1+y2-1 修改++ 如果y3>=x break;

　　可以发现，如果（y1,y2,y3）有一个边>=x，则还需两步即可完成。

　　输出 修改+2

AC Code:

 1 #include<bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5     int x,y,ans; 6     while(scanf("%d%d",&x,&y)!=EOF) 7     { 8         ans=0; 9         int y1,y2,y3;10         y1=y2=y3=y;11         while(y1!=x&&y2!=x&&y3!=x)12         {13             y1=y2+y3-1;14             ++ans;15             if(y1>=x)break;16             y2=y1+y3-1;17             ++ans;18             if(y2>=x)break;19             y3=y1+y2-1;20             ++ans;21             if(y3>=x)break;22         }23         cout<<ans+2<<endl;24     }25     return 0;26 }

 

codeforces 712C C. Memory and De-Evolution(贪心)


联系
我们