洛谷P2660 zzc 种田

2018-06-17 21:35:30来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目背景

可能以后 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;
}

  

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:UVA_10139

下一篇:洛谷P1567 统计天数