蓝桥杯备考:贪心+思维题 之 zzc种田
这道题也算是一道贪心题,注意我们的xy最大是10的16次方,我们不要忘了用long long
如图,我们可以先把最大的正方形全部挑出去,也就是我们得用宽来当正方形的边长,然后把大正方形全部挑出去
长是x 宽是y,我们用宽作为边长,我们让长除宽就是我们能挑出去的大正方形,如图我们把两个3*3的大正方形挑了出去 然后我们让长%宽,也就是我们新的长,如图是2,长变成宽了,我们要swap一下长和宽
接下来我们还是挑出去最大的,我们让长除宽,挑出去一个2*2的大正方形,然后长变成1,宽还是2,我们还是交换长和宽,继续让长/宽,然后让长%宽,这时候长变成0了,我们循环结束,
好的,过程模拟完了,我们来实现一下代码吧!
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
ll x,y;
cin >> x >> y;
ll cnt = 0;
ll ret = 0;
//x是长,y是宽
while(x && y)
{
cnt=x/y;
x%=y;
ret+=cnt*y*4;
swap(x,y);
}
cout << ret << endl;
}