蓝桥杯学习笔记(贪心)

在很久很久以前,有几个部落居住在平原上,依次编号为1到n。第之个部落的人数为 t
有一年发生了灾荒,年轻的政治家小蓝想要说服所有部落一同应对灾荒,他能通过谈判来说服部落进行联台。
每次谈判,小蓝只能邀请两个部落参加,花费的金币数量为两个部落的人数之和,谈判的效果是两个部落联合成一个部落(人数为原来两个部落的人数之和)。
输入描述
输入的第一行包含一个整数 1,表示部落的数量第二行包含 几个正整数,依次表示每个部落的人数。

这道题我用了两种方法 

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int sum = 0;
        System.out.println(getMin(a, sum));

    }

    public static int getMin(int[] a, int sum) {
        if (a.length == 2) {
            return sum + a[0] + a[1];
        } else {
            Arrays.sort(a);
            int[] aa = new int[a.length - 1];
            for (int i = 2; i < a.length; i++) {
                aa[0] = a[0] + a[1];
                aa[i - 1] = a[i];
            }
            sum += aa[0];
            return getMin(aa, sum);
        }
    }
public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(sc.nextInt());
        }
        Collections.sort(list);
        int sum = 0;
        while (list.size() > 1) {
            int num = list.get(0) + list.get(1);
            sum += num;
            list.remove(0);
            list.remove(0);
            list.add(num);
            Collections.sort(list);
        }
        System.out.println(sum);
    }

解题主要思想是贪心,只要搞明白之后就能理解了

循环排序 数组或集合计算前两个值之和 放入新数组 再让和累加。最后得到结果

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/486094.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

打通数字化最后一公里,就是数据释放价值的最后一公里;

前 言 2023年底&#xff0c;中共中央、国务院正式印发《关于构建数据基础制度更好发挥数据要素作用的意见》(以下简称《数据二十条》)&#xff0c;明确提出探索数据资产入表新模式&#xff0c;要积极探索数据资产入表的可行路径&#xff0c;加快推动数据入表的实施进度&…

RK3568平台开发系列讲解(Linux系统篇)设备树中时钟描述

🚀返回专栏总目录 文章目录 一、时钟生产者(Clock Provider)1.1、clock-cells1.2、clock-frequency1.3、assigned-clocks 和 assigned-clock-rates1.4、clock-indices1.5、assigned-clock-parents二、时钟消费者(Clock Consumer)2.1、clocks

Matlab之已知2点绘制长度可定义的射线

目的&#xff1a;在笛卡尔坐标系中&#xff0c;已知两个点的位置&#xff0c;绘制过这两点的射线。同时射线的长度可以自定义。 一、函数的参数说明 输入参数&#xff1a; PointA&#xff1a;射线的起点&#xff1b; PointB&#xff1a;射线过的零一点&#xff1b; Length&…

【微服务】认识Dubbo+基本环境搭建

认识Dubbo Dubbo是阿里巴巴公司开源的一个高性能、轻量级的WEB和 RPC框架&#xff0c;可以和Spring框架无缝集成。Dubbo为构建企业级微服务提供了三大核心能力&#xff1a; 服务自动注册和发现、面向接口的 远程方法调用&#xff0c; 智能容错和负载均衡官网&#xff1a;https…

unity 添加newtonsoft-json

再git url上添加&#xff1a;com.unity.nuget.newtonsoft-json

seata测试demo(订单)

seata工作流程: seata对分布式事务的协调和控制就是31 1>XID&#xff1a;XID是全局事务的唯一标识&#xff0c;它可以在服务的调用链路中传递&#xff0c;绑定到服务的事务上下文中。 3>TC->TM->RM TC:事务协调器>就是seata 负责维护全局事务和分支事务的状…

Window平台应用程序打包(用Microsoft Visual Studio Installer Projects制作安装包)

window平台应用程序打包&#xff08;用Microsoft Visual Studio Installer Projects制作安装包&#xff09; 在window平台使用Visual Studio 开发完后&#xff0c;一般都需要打包成一个安装包文件 使用Visual Studio 自带的打包插件打包&#xff1a; 1 安装project setup打包…

Day 15 Servlet(一)

Servlet 1、简介2、快速入手2.1servlet jar包导入2.2 Content-type2.3 Servlet-url 写法2.4 注解方式配置servlet2.5 servlet 生命周期 1、简介 资源包括静态资源和动态资源。 对于服务器响应&#xff0c;有时候我们需要根据客户的不同请求返回不同的数据和页面。此时就需要一…

代码随想录训练营第55天 | LeetCode 583. 两个字符串的删除操作、​​​​​​LeetCode 72. 编辑距离、总结

目录 LeetCode 583. 两个字符串的删除操作 文章讲解&#xff1a;代码随想录(programmercarl.com) 视频讲解&#xff1a;LeetCode&#xff1a;583.两个字符串的删除操_哔哩哔哩_bilibili 思路 ​​​​​​LeetCode 72. 编辑距离 文章讲解&#xff1a;代码随想录(programm…

一、Jdk和eclipse安装和配置

1 JDK与eclipse的安装和配置 1.1JDK安装 1.2配置环境变量 &#xff08;1&#xff09;新建系统变量名为java_home,变量值为jdk安装路径&#xff0c;由自己决定&#xff0c;例如&#xff1a;C:\Program Files\Java\jdk-11.0.6 (2))新建系统变量名为classpath,变量值为".&q…

MySQL事务(超详细!!!)

目录 一、MySQL事务的概念 二、事务的ACID特点 1、原子性&#xff08;Atomicity&#xff09; 2、持久性 3、隔离性&#xff08;Isolation&#xff09; 3.1 事务的并发问题 ①、脏读(读取未提交数据) ②读已提交、不可重复读(前后多次读取&#xff0c;数据内容不一致) …

数学算法(算法竞赛、蓝桥杯)--判定质数试除法

1、B站视频链接&#xff1a;G06 判定质数 试除法_哔哩哔哩_bilibili 题目链接&#xff1a;【深基7.例2】质数筛 - 洛谷 #include <bits/stdc.h> using namespace std;bool is_prime(int x){if(x1)return 0;//特判1不是质数for(int i2;i*i<x;i){//枚举小的那个到根号n…

算法系列--动态规划--子序列(1)

&#x1f495;"深思熟虑的结果往往就是说不清楚。"&#x1f495; 作者&#xff1a;Mylvzi 文章主要内容&#xff1a;算法系列–动态规划–子序列(2) 今天带来的是算法系列--动态规划--子序列(1),是子序列问题的开篇!带大家初识子序列问题 一.什么是子序列问题 我们…

LeetCode 热题 HOT 100(P21~P30)

系列文章&#xff1a; LeetCode 热题 HOT 100(P1~P10)-CSDN博客 LeetCode 热题 HOT 100(P11~P20)-CSDN博客 LeetCode 热题 HOT 100(P21~P30)-CSDN博客 LC48rotate_image . - 力扣&#xff08;LeetCode&#xff09; 题目&#xff1a; 给定一个 n n 的二维矩阵 matrix 表…

Practical Network Acceleration with Tiny Sets

文章目录 why-AbstractIntroductionContributionsRelated WorksFilter-level pruningBlock-level pruningData Limited Knowledge DistillationMethodOverviewThe motivation to drop blocksThe recoverability of the pruned modelRecover the accuracy of the pruned modelEx…

力扣:205. 同构字符串

前言&#xff1a;剑指offer刷题系列 问题&#xff1a; 给定两个字符串 s 和 t &#xff0c;判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t &#xff0c;那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符&#xff0c;同时不改变字符…

Leetcode——560. 和为 K 的子数组

560. 和为 K 的子数组 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/subarray-sum-equals-k/description/ 题目描述&#xff1a; 给你一个整数数组 nums 和一个整数 k &#xff0c;请你统计并返回该数组中和为 k 的子数组的个数 。子数组是数组中元素…

ABeam德硕|中国与柴火创客空间达成战略合作,拟定联合发布企业数字化转型实战课程

引言 随着近年数字技术的迅速发展&#xff0c;企业纷纷寻求数字化转型&#xff0c;而数字化转型企业人才的培养正是其中的关键一环。数字化转型人才能够从战略层面把握转型方向&#xff0c;快速适应新技术变革&#xff0c;有效应用技术工具以优化业务流程、提高组织效率、实践创…

如何配置元数据?(如何使用Spring容器)

目录 一、引出问题&#xff08;如何配置元数据&#xff1f;&#xff09;二、没有Spring的时代三、XML配置文件&#xff08;xml配bean&#xff09;1 格式1.1 示例 2 实例化一个Spring容器3 使用Spring容器4 后言 四、基于注解的配置 【[1.9. Annotation-based Container Configu…

代码随想录算法训练营第五十四天|392.判断子序列、115.不同的子序列

392.判断子序列 刷题https://leetcode.cn/problems/is-subsequence/description/文章讲解https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html视频讲解https://www.bilibili.com/video/BV1tv4y1B7ym/?vd_sourceaf4853e80f89e28094a5fe1e220…