洛谷P2660 zzc 种田
题目背景
可能以后 zzc就去种田了。
题目描述
田地是一个巨大的矩形，然而zzc 每次只能种一个正方形,而每种一个正方形时zzc所花的体力值是正方形的周长，种过的田不可以再种，zzc很懒还要节约体力去泡妹子，想花最少的体力值去种完这块田地，问最小体力值
输入输出格式
输入格式：
两个正整数x,y，表示田地的长和宽
输出格式：
输出最小体力值
输入输出样例
输出样例#1：
1 10输出样例#1： 复制
40输入样例#2：
2 2 输出样例#2：
8说明
1<=x,y<=10^16
首先每次种最大的肯定是最优的
然后就有30分啦
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int MAXN=101;
inline int read()
{
char c=getchar();int flag=1,x=0;
while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;
}
LL x,y,ans=0;
int main()
{
cin>>x>>y;
while(x!=0&&y!=0)
{
int h=min(x,y);
if(x>y) x-=h;
else y-=h;
ans+=h*4;
}
cout<<ans;
return 0;
}我们考虑优化这个操作
就拿第一组样例来说
每次都种一个1*1的肯定太慢了
我们看一下能种几个1*1的，然后全加上就可以了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL unsigned long long
using namespace std;
const int MAXN=101;
inline int read()
{
char c=getchar();int flag=1,x=0;
while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;
}
LL x,y,ans=0;
int main()
{
cin>>x>>y;
while(x!=0&&y!=0)
{
if(x>y) swap(x,y);
LL h=y/x;
ans+=h*x*4;
y=y%x;
}
cout<<ans;
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-11-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录