【题目描述】

给定一个边长为xx的正三角形,现在每秒钟你可以改变其中一条边的长度(修改量整数),在改变过程中,每秒钟都需要保证改变后的三角形是合法的,且变成均为正整数。

现在需要最终把三角形改变成边长为y的正三角形,请计算至少需要几秒钟。

【思路分析】

比赛的时候想到了用贪心,但是策略错了,导致WA掉(运气好竟然有90分

正解:贪心

下面讲一个比较方便的方法:
题目要求从大三角形转化成小三角形,我们以下面这组数据为例

22   4
一种可行方案:
(22,22,22);(7,22,22);(7,22,16);(7,10,16);
(7,10,4);(7,4,4);(4,4,4)

发现: 如果从大到小看,我们发现改变的第一条边很难具体判断改成多大

解决方案:

不如倒过来看,把小三角形转成大三角形,并不改变最终答案

每次将最小的一条边改成能达到的最大值(由于是整数,那么即另外两边的和-1)
注意一点:如果能达到的最大值已经大于x值了,那么就取x;

代码:

#include<cstdio>
#include<cmath>
#include<cctype>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
using namespace std;
inline int read()
{
    char chr=getchar();
    int f=1,ans=0;
    while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
    while(isdigit(chr))  {ans=(ans<<1)+(ans<<3)+chr-'0';chr=getchar();}
    return ans*f;
}

inline void kai()
{
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
}
int x,y;
int a,b,c;
int ans=0;
void ssort(){//三个值排序
    if(a>b) swap(a,b);
    if(a>c) swap(a,c);
    if(b>c) swap(b,c);
}
int main(){
    //kai();
    x=read();
    y=read();
    a=b=c=y;//三边都赋值为最小的边
    while(a<x||b<x||c<x){//只要三边中有一边没有达到x就继续循环
        ssort();//三边排序
        int t=c+b-1;//能达到的最大值
        a=min(x,t);//与x比,取小的
        ans++;//修改了一次
    }
    cout<<ans;
    return 0;
}