贪心算法C++

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

一、分发饼干

    1、题目:

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子 i,都有一个胃口值  g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

    2、代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 3 * 1e5;
int s[N];
int g[N];
int n, m;
int main() {
    cin >> n, m;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    for (int j = 0; j < m; j++) {
        cin >> g[j];
    }
    sort(s,s+n);
    sort(g,g+m);
    int result = 0;
    int index = m - 1;
    for (int j = m-1; j >=0; j--) {
        while (index >= 0 && s[index] >= g[j]) {
            result++;
            index--;
        }
    }
    cout << result;
    return 0;
}

二、摆动序列

    1、题目:

给定一个整数序列,返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。

    2、代码:

#include<iostream>
using namespace std;
int nums[1010];
int n;
int main() {
    cin >> n;
    for (int i = n; i < n; i++) {
        cin >> nums[i];
    }
    if (n <= 0) {
        cout << n;
    }
    int prediff = 0;
    int curdiff = 0;
    int result = 1;
    for (int i = 1; i < n - 1; i++) {
        curdiff = nums[i +1] - nums[i];
        if (prediff <= 0 && curdiff > 0|| prediff >= 0 && curdiff < 0) {
            result++;
        }
        prediff = curdiff;
    }
    cout << result;
    return 0;
}

三、最大连续子序列和

    1、题目:

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

    2、代码:

#include<iostream>
using namespace std;
const int N = 1e6;
int n;
int nums[N];
int mian() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    if (n == 0) {
        cout << 0;
    }
    int count = 0;
    int result = INT_MIN;
    for (int i = 0; i < n; i++) {
        count += nums[i];
        if (count > result) {
            result = count;
        }
        if (count <=0) {
            count = 0;
        }
    }
    cout << result;
    return 0;
}

四、k次取反后最大化数组和

    1、题目:

给定一个整数数组 A,我们只能用以下方法修改该数组:我们选择某个索引 i 并将 A[i] 替换为 -A[i],然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。)

以这种方式修改数组后,返回数组可能的最大和。

    2、代码

#include<iostream>
#include<algorithm>
using namespace std;
int nums[100010];
int n,k;
bool cmp(int a, int b) {
    for (int i = 0; i < n; i++) {
        if (nums[i] < 0) {
            nums[i] *= -1;
        }
    }
    return nums[a] > nums[b];
}
int mian() {
    cin >> n>>k;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    sort(nums, nums + n, cmp);
    for (int i = 0; i < n; i++) {
        if (nums[i] < 0&&k>0) {
            nums[i] *= -1;
            k--;
        }
    }
    if (k %2==1) {
        nums[n - 1] *= -1;
    }
    int result = 0;
    for (int i = 0; i < n; i++) {
        result += nums[i];
    }
    cout << result;
    return 0;
}
文章来源地址https://www.toymoban.com/news/detail-844878.html

到了这里,关于贪心算法C++的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++ 求最大子序列和(贪心算法)

    #include \\\"iostream\\\" #include \\\"vector\\\" using namespace std; class Solution { // 得到一个最大的负数 int isAllLow(vectorint nums){ int max=nums[0]; for (int i = 1; i nums.size(); ++i) { if(maxnums[i]){ max=nums[i]; } } return max; } public: // 求最大子序列 int maxSubArray(vectorint nums) { int sum=0; int maxsum=this-isAllLow(nums); // 如果是一个

    2024年02月07日
    浏览(43)
  • 秒懂百科,C++如此简单丨第二十天:贪心算法2

    目录 Everyday English 前言 洛谷 P1031 均分纸牌 题目描述 思路点拨 AC代码 洛谷 P1094 纪念品分组 题目描述 样例输入 样例输出  思路点拨 AC代码 洛谷 P2660 zzc 种田  题目描述 思路点拨 AC Code 结尾 Don\\\'t miss the opportunity. 机不可失,时不再来。 这节课是贪心算法的习题课,我们会讲解

    2024年02月20日
    浏览(40)
  • 2023华为OD机试真题【区间交叠/贪心算法】【Python Java C++】

    给定坐标轴上的一组线段,线段的起点和终点均为整数并且长度不小于1,请你从中找到最少数量的线段,这些线段可以覆盖住所有线段。 输入描述 第一行输入为所有线段的数量,不超过10000,后面每行表示一条线段,格式为”x,y”, x和y 分别表示起点和终点,取值范围是

    2024年02月13日
    浏览(56)
  • 算法分析与设计-会场安排问题(贪心)(通俗易懂,附源码和图解,含贪心选择性质和最优子结构性质的证明)(c++)

    (一)题目 问题描述 假设在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点有着不同颜色的最小着色数,相当于

    2024年02月07日
    浏览(95)
  • 贪心算法问题实验:贪心算法解决TSP问题

    TSP问题是指旅行商问题,即给定一组城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中有着广泛的应用。 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最

    2024年02月03日
    浏览(44)
  • 算法竞赛备赛之贪心算法训练提升,贪心算法基础掌握

    905.区间选点 给定N个闭区间[ai, bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量,位于区间端点上的点也算作是区间内。 将每个按区间的右端点从小到大排序 从前往后依次枚举每个区间 如果当前区间中已经包含点,则直

    2024年02月08日
    浏览(37)
  • 【基础算法】贪心算法

    贪心算法又称贪婪算法,是一种常见的算法思想。贪心算法的优点是效率高,实现较为简单,缺点是可能得不到最优解。 贪心算法就是在求解问题时,总是做出当前看来最好的选择。也就是说贪心算法并不从整体最优上考虑问题,算法得到的是局部最优解。而局部最优解叠加

    2024年02月12日
    浏览(43)
  • 算法 - 动态规划 / 贪心算法

    🥂 🌸 121. 买卖股票的最佳时机 [数组] [股票] (动态规划) 🥂 🌸 122. 买卖股票的最佳时机Ⅱ [数组] [股票] (动态规划) 🥂 🌸 123. 买卖股票的最佳时机Ⅲ [数组] [股票] (动态规划) 🥂 🌸 188. 买卖股票的最佳时机Ⅳ [数组] [股票] (动态规划) 🥂 🌸 309. 买卖股票的最佳时机含冷冻

    2024年01月17日
    浏览(38)
  • 算法-贪心算法

    题目:给定一个字符串str,只由‘X’和‘.’两种字符构成。‘X’表示墙,不能放灯,也不需要点亮‘.’表示居民点,可以放灯,需要点亮如果灯放在i位置,可以让i-1,i和i+1三个位置被点亮返回如果点亮str中所有需要点亮的位置,至少需要几盏灯 思路:递归方式,每个位置

    2024年02月21日
    浏览(39)
  • 初级算法-贪心算法

    主要记录算法和数据结构学习笔记,新的一年更上一层楼! 贪心算法 本质找到每个阶段的局部最优,从而推导全局最优 1. 题目 :假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。 对每个孩子 i,都有一个胃口值 g[i],这是能让

    2024年02月03日
    浏览(30)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包