c++算法之贪心

发布时间:2024年01月19日

目录

贪心算法介绍

贪心算法实现步骤

常见贪心模型和例题

例题1

问题描述

输入格式

输出格式

样例输入

样例输出

说明

例题2 谈判

题目描述

输入描述

输出描述

输入输出样例

示例 1

运行限制

例题3 纪念品分组

题目描述

输入描述

输出描述

输入输出样例

示例 1

运行限制

例题4 分糖果

问题描述

输入描述

输出描述

样例输入

样例输出

说明


贪心算法介绍

贪心的基本原理:每一步都选择局部最优解,而尽量不考虑对后续的影响,最终达到全局最优解

贪心的局限性:贪心算法不能保证获得全局最优解,但在某些问题上具有高效性。

贪心的特征:贪心选择性质、最有子结构性质

贪心算法实现步骤

1.确定问题的最优子结构(贪心往往和排序、优先队列一起出现)

2.构建贪心选择的策略,可能通过“分类讨论”、“最小代价”、“最大价值”等方式来思考贪心策略。简单验证贪心的正确性,采用句:这样做一定不会使结果变得更差、不存在比当前方案更好的方案。

3.通过贪心选择逐步求解问题,直到得到最终解

常见贪心模型和例题

例题1

问题描述

小蓝是机甲战队的队长,他手下共有 nn 名队员,每名队员都有一个战斗力值 wiwi?。现在他需要将这 nn 名队友分成两组 aa 和 bb,分组必须满足以下条件:

  • 每个队友都属于 aa 组或 bb 组。
  • aa 组和 bb 组都不为空。
  • 战斗力差距最小。

战斗力差距的计算公式为 ∣max?(a)?min?(b)∣∣max(a)?min(b)∣,其中 max?(a)max(a) 表示 aa 组中战斗力最大的,min?(b)min(b) 表示 bb 组中战斗力最小的。

请你计算出可以得到的最小战斗力差距。

输入格式

第一行一个整数 nn,表示队员个数。

第二行 nn 个整数 w1,w2,w3....wnw1?,w2?,w3?....wn?,分别表示每名队友的战斗力值。

数据范围保证:2≤n≤1052≤n≤105,1≤wi≤1091≤wi?≤109。

输出格式

输出一个整数,表示可以得到的最小战斗力差距。

样例输入

3
1 2 3

样例输出

1

说明

样例中,当 a=[1,3]a=[1,3],b=[2]b=[2],此时战斗力差距为 11,无法得到比 11 更小的安排方式。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 5;
int a[N];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];
	sort(a + 1, a + 1 + n);
	int ans = a[2] - a[1];
	for (int i = 1; i < n; ++i)ans = min(ans, a[i + 1]-a[ i ]);
	cout << ans << endl;

	return 0;
}

例题2 谈判

题目描述

在很久很久以前,有 nn 个部落居住在平原上,依次编号为 11 到 nn。第 ii 个部落的人数为 titi?。

有一年发生了灾荒。年轻的政治家小蓝想要说服所有部落一同应对灾荒,他能通过谈判来说服部落进行联合。

每次谈判,小蓝只能邀请两个部落参加,花费的金币数量为两个部落的人数之和,谈判的效果是两个部落联合成一个部落(人数为原来两个部落的人数之和)。

输入描述

输入的第一行包含一个整数 nn,表示部落的数量。

第二行包含 nn 个正整数,依次表示每个部落的人数。

其中,1≤n≤1000,1≤ti≤1041≤n≤1000,1≤ti?≤104。

输出描述

输出一个整数,表示最小花费。

输入输出样例

示例 1

输入

4
9 1 3 5

输出

31

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
using ll = long long;
priority_queue<ll,vector<ll>,greater<ll>>pq;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
	{
		ll x; cin >> x;
		pq.push(x);
	}
	ll ans = 0;
	while (pq.size() > 1)
	{
		//说明存在至少两个部落
		ll x = pq.top(); pq.pop();
		ll y = pq.top(); pq.pop();

		ans += x + y;
		pq.push(x + y);
	}
	cout << ans << endl;

	return 0;
}

例题3 纪念品分组

题目描述

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

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

输入描述

第 1 行包括一个整数 w?(80≤w≤200)w?(80≤w≤200),为每组纪念品价格之和的上限。

第 2 行为一个整数 n?(1≤n≤30000)n?(1≤n≤30000),表示购来的纪念品的总件数。

第3 ~ nn+2行每行包含一个正整数 pi?(5≤pi≤w)pi??(5≤pi?≤w),表示所对应纪念品的价格。

输出描述

输出一行,包含一个整数,即最少的分组数目。

输入输出样例

示例 1

输入

100
9
90
20
20
30
50
60
70
80
90

输出

6

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

#include <iostream>
#include<algorithm>
using namespace std;
const int N = 30005;
int a[N];
int main()
{
    int w; cin >> w;//价格上限
    int n; cin >> n;//纪念品件数
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    int l = 1; int r = n; int ans = 0;
    while (l <= r)
    {
        ans++;
        if (l == r)
        {
            break;
        }
        if (a[l] + a[r] <= w)
        {
            l++, r--;
        }
        else
        {
            r--;
        }
    }
    cout << ans << endl;
    // 请在此输入您的代码
    return 0;
}

例题4 分糖果

问题描述

最近暑期特训算法班的同学们表现出色,他们的老师肖恩决定给他们分发糖果。肖恩购买了 nn 个不同种类的糖果,用小写的阿拉伯字母表示。每个糖果必须分发给一个同学,并且每个同学至少要分到一个糖果。同学们的开心程度定义为他们所分到的糖果组成的字符串 s[i]s[i] 的字典序。肖恩希望同学们的开心程度相差尽量小,因此他要找到一种方案,使得所有糖果组成的字符串中字典序最大的字符串尽可能小。请输出能够实现字典序最小可能的 max?(s[1],s[2],s[3],...,s[x])max(s[1],s[2],s[3],...,s[x]) 。

输入描述

第一行输入两个整数 nn 和 xx ,分别表示有 nn 个糖果 xx 个同学。

第二行输入一个长度为 nn 的字符串 SS , S[i]S[i] 表示第 ii 个糖果的种类。

数据保证 1≤n≤106,1≤x≤n,S[i]∈[′a′,′z′]1≤n≤106,1≤x≤n,S[i]∈[′a′,′z′] 。

输出描述

输出一个字符串,为所有糖果组成的字符串中字典序最大的字符串最小的可能值。

样例输入

6 2
caabdc

样例输出

abccd

说明

一个最优分配方案是一个同学拿到 abccdabccd ,一个同学拿到 aa 。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 9;
char s[N];
int main()
{
	int n, x; cin >> n >> x;
	cin >> s + 1;
	sort(s + 1, s + 1 + n);
	if (s[1] == s[n])//全部相等
	{
		for (int i = 1; i <= n / x + (n % x ? 1 : 0); i++)
		{
			cout << s[1];
		}
	}
	else if (s[1] == s[x])
	{
		for (int i = x; i <= n; i++)cout << s[i];
	}
	else
	{
		cout << s[x];
	}
	return 0;
}

文章来源:https://blog.csdn.net/weixin_63201442/article/details/135695434
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。