洛谷P2660 zzc 种田

题目链接：P2660 zzc 种田 - 洛谷 | 计算机科学教育新生态

题目难度：普及一

题目背景

可能以后 zzc 就去种田了。

题目描述

田地是一个巨大的矩形，然而 zzc 每次只能种一个正方形,而每种一个正方形时 zzc 所花的体力值是正方形的周长，种过的田不可以再种，zzc 很懒还要节约体力去泡妹子，想花最少的体力值去种完这块田地，问最小体力值。

输入格式

两个正整数 x,y，表示田地的长和宽。

输出格式

输出最小体力值。

样例 

样例输入1

1 10
样例输出1

40

样例2

样例输入2

2 2

样例输出 2

8

题目分析：这道题是一道贪心题，但是需要一些小小的优化。

首先，让我们来模拟一组数据：输入：2  11，易知最大可以先裁剪出5个边长为2的正方形，然后再裁剪出一个正方形，不难发现,每次都切一个边长为min(x,y)正方形，然后将短的那一边减掉这个边长，答案加上边长∗4即可。直到x和y中有一个为0就结束。

直接上代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10010;
ll ans;
ll x,y; 

ll read()
{
	ll s=0,f=1;
	char ch=getchar();
	
	while (ch<'0'||ch>'9')
	{
   	   if (ch=='-') f=-1;
	   ch=getchar();
	}
	while (ch>='0'&&ch<='9')
	{
	   s=s*10+ch-'0';
	   ch=getchar();
	}
	return s*f;
}

int main() {
   
    x = read(),y = read();
    if(y > x) swap(x,y);
    
    while(true)
    {
    	ans += x / y * 4 * y;
    	x -= x/y * y;
    	if(y > x) swap(x,y);
    	if(x == 0 || y == 0) break;
    	
	}
	cout<<ans;
    return 0;
}