秒懂百科，C++如此简单丨第二十天：贪心算法2-Toy模板网

这篇具有很好参考价值的文章主要介绍了秒懂百科，C++如此简单丨第二十天：贪心算法2。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Everyday English

前言

洛谷 P1031 均分纸牌

题目描述

思路点拨

AC代码

洛谷 P1094 纪念品分组

题目描述

样例输入

样例输出

思路点拨

AC代码

洛谷 P2660 zzc 种田

题目描述

思路点拨

AC Code

结尾

Everyday English

Don't miss the opportunity.

机不可失，时不再来。

前言

这节课是贪心算法的习题课，我们会讲解三道题目。

贪心算法1：贪心算法第一节课

洛谷 P1031 均分纸牌

题目网址：[NOIP2002 提高组] 均分纸牌 - 洛谷

题目描述

有 N 堆纸牌，编号分别为 1,2,……,N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N−1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

例如 N=4 时，4堆纸牌数分别为 9,8,17,6。

移动 3 次可达到目的：

从第三堆取 4 张牌放到第四堆，此时每堆纸牌数分别为 9,8,13,10。
从第三堆取 3 张牌放到第二堆，此时每堆纸牌数分别为 9,11,10,10。
从第二堆取 1 张牌放到第一堆，此时每堆纸牌数分别为 10,10,10,10。

思路点拨

首先，我们得知道每堆牌应有多少张。题目保证了总牌数是堆数的倍数，那么最终每一堆的牌数应该是(a[1]+a[2]+……+a[N])/N，也就是N堆牌的平均数。

比如有4堆牌，分别是有2、3、4、7张，而平均数就是4，也就是最后每堆牌所分得的张数。

每一堆牌的张数只可能有三种情况：

1.比平均值小：少几张，就让右边的一堆给几张。

2.和平均值相同：不需要给，判断下一个。

3.比平均值大：多几张，就把多的给右边。

情况一时，右边一堆的张数可能会出现负数，但没有关系，最终还是会有其他堆补回来的。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int n,a[maxn],cnt;
int main()
{
    int mean,sum=0;
	cin>>n;
	for(int i=1;i<=n;i++)
    {
		cin>>a[i];
		sum+=a[i];
	}
	mean=sum/n; //☆总和÷堆数=平均每堆牌数 
	for(int i=1;i<=n-1;i++)
	{
		if(a[i]!=mean) 
        {
			a[i+1]+=a[i]-mean;//a[i]少的话会加上负数，相当于减少右边的牌
			cnt++;
		}
	}
	cout<<cnt<<endl;
	return 0;
}

洛谷 P1094 纪念品分组

题目网址：[NOIP2007 普及组] 纪念品分组 - 洛谷

题目描述

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

样例输入

样例输出

思路点拨

相信各位都学过首尾配对吧，比如计算下面这道题：

1+2+3+4+5+6+7+8+9

除了利用公式计算，我们还可以首尾配对，观察首和尾，很容易想到1+9=10，而总共有4组余下一个5，即4×10+5=45。

而这一题要尽可能的平均不就是首尾配对吗？但要注意一点，不能超过给定范围。

既然要首尾配对，首先得排个序吧，这就要用到我们学过的sort函数了。

接着我们分析一下样例，先把样例排序一下：

20 20 30 50 60 70 80 90 90

利用配对的思想：最小+最大=20+90=110，超过了限制，也就是说，最大的只能单独一个组。

再次利用配对的思想：最小+第二大=20+90=110，还是大了，第二大也只能单独一组。

再次利用配对的思想：最小+第三大=20+80=100，没有超过限制，可以为一组。

再次利用配对的思想：第二小+第四大=20+70=90，没有超过限制，可以为一组。

以此类推，我们便可得出答案。

而模拟两边不断往里缩小范围的不就是指针吗！上代码！

AC代码

#include<bits/stdc++.h>
using namespace std;
int n, w, ans;
int a[30010];
int main() 
{
    cin>>w>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);//要想配对，先排序
    int i=1,j=n;//i,j为两个指针
    while(i<=j) 
    {
        if (a[i]+a[j]<=w)//两个纪念品可以为一组
        {
            i++;
            j--;
            ans++;
        } 
        else//最大单独为一组
        {
            j--;
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

洛谷 P2660 zzc 种田

题目网址：zzc 种田 - 洛谷

题目描述

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

思路点拨

很明显的一道贪心题，要想耗费力气最小，肯定是每次划分尽可能大的正方形。

比如2×2的一个田地，如果你划分成4个1×1的需要周长：1×4×4=16cm

而划分成1个2×2的只需要周长：2×4=8cm

所以，贪心策略是：每次划分尽可能大的正方形。

对于3×5的正方形，最省力气的划分如下：

秒懂百科，C++如此简单丨第二十天：贪心算法2,秒懂百科，C++如此简单,c++,贪心算法,开发语言

注意：最大的正方形应该已较短的一条边作为边长。

90分

#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
signed main()
{
	ll x,y,l,ans=0;
	cin>>x>>y;
	l=x*y;//l为剩余面积
	if(x>y) swap(x,y);//始终保持小的是x
	while(l!=0)
	{
		l-=x*x;//画一个尽可能大的正方形
		y-=x;
		ans+=x*4;
		if(x>y) swap(x,y);
	}
	cout<<ans<<endl;
}

优化：不一定一个一个地划分，可以一起划分。

AC Code

#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
signed main()
{
	ll x,y,ans=0;
	cin>>x>>y;
	if(x>y) swap(x,y);
	while(x!=0&&y!=0)
	{
		ans+=x*4*(y/x);
		y%=x;
		swap(x,y);
	}
	cout<<ans<<endl;
}