贪心+蓝桥杯

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

原题路径

题目思路 : 思路很简单,肯定是贪心做法,要使总代价最小,需用那些出现次数比avg多的数来替换那些没有出现或者是出现次数少于avg的数, 所以我们存当前数每次出现的代价是多少 ,枚举每一个 0 - 9 之间的数 ,如果当前数出现的次数多于avg,那么说明需要减少,每次用最小的代价替换即可
由于我们并不知道替换的数是哪一个,但由于题目中说明了每个数都会出现 n / 10 次,所以证明一旦多出来的数必定会替换为另一个数,故我们只需要从小到大替换,将 avg 个当前数中价值最大的保存即可。文章来源地址https://www.toymoban.com/news/detail-808884.html

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N] , b[N];
vector<int> h[N];

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)
    {
        int a , b;
        cin >> a >> b;
        h[a].push_back(b);
    }
    
    int avg = n / 10;
    long long res = 0;
    for(int i = 0 ; i < 10 ; i ++)
    {
        int x = h[i].size();
        if(x > avg)
        {
            sort(h[i].begin() , h[i].end());
            for(int j = 0 ; j < h[i].size() - avg ; j ++)
            {
                res += h[i][j];
            }
        }
    }
    
    printf("%lld" , res);
    
    return 0;
}

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

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

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

相关文章

  • 蓝桥杯C组-填充-贪心

    点击此处查看原题​​​​​​​ *思路:首先要求 00 11 尽可能的多,所以尽可能多的多配对,配对只在i , i + 1之间发生,所以只需要关注str[i] 和 str[i + 1]即可,如果str[i] == str[i + 1] ,那么一定配对,res ++ , 否则说明只有 str[i] == 0 str[i + 1] == 1 或者 str[i] == 1 str[i + 1] == 0 两种情

    2024年01月18日
    浏览(24)
  • 题目 3158: 蓝桥杯2023年第十四届省赛真题-三国游戏(贪心)

    小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵X, Y, Z (一开始可以认为都为 0 )。游戏有 n 个可能会发生的事件,每个事件之间相互独立且最多只会发生一次,当第 i 个事件发生时会分别让 X, Y, Z 增加Ai , Bi ,Ci 。 当游戏结束时 (所有事件的发生与否已经确

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

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

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

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

    2024年02月08日
    浏览(35)
  • 贪心算法part04 算法

    ● 860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球 https://leetcode.cn/problems/lemonade-change/description/ https://leetcode.cn/problems/queue-reconstruction-by-height/description/ https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/

    2024年01月17日
    浏览(38)
  • 算法 - 动态规划 / 贪心算法

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

    2024年01月17日
    浏览(37)
  • 【算法】—贪心算法详解

    ①贪心算法的概念 : 贪心算法就是不断选择 在当前看来最好的选择,也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择 虽然贪心算法不能对所有问题都得到整体最优解,但在一些情况下,即使贪心算法 不一定能得到整体最优解 ,其

    2024年02月04日
    浏览(44)
  • 算法-贪心算法

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

    2024年02月21日
    浏览(36)
  • 贪心算法part03算法

    ● 1005.K次取反后最大化的数组和 ● 134. 加油站 ● 135. 分发糖果 https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/ https://leetcode.cn/problems/gas-station/description/ https://leetcode.cn/problems/candy/description/

    2024年01月18日
    浏览(44)
  • 【算法】贪心算法练习一

    个人主页 : zxctscl 如有转载请先通知 一、贪心策略:解决问题的策略,局部最优-全局最优 把解决问题的过程分为若干步; 解决每一步的时候,都选择当前看起来“最优的”解法; 希望得到全局最优。 二、贪心策略的正确性 因为有可能“贪心策略”是一个错误的方法 正确

    2024年04月25日
    浏览(70)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包