IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【贪心算法】手办合并 -> 正文阅读

[数据结构与算法]【贪心算法】手办合并

题目描述
在这里插入图片描述
分析
首先要明白5点

  1. 想要保证距离最短每个手办必须只朝一个方向(左/右)移动n米(总不可能先左后右这样折返,得不偿失)
  2. 每个手办的移动操作可以分解成更细小的按照一米一米的移动操作,比如一个手办向右移动4米就可以分解为四个向右移动一米的操作
  3. 在2前提下会出现手办移动后和另一个手办位置重叠的情况,这个时候重叠的两个手办就可以合并,新的权值就是两个手办权值之和
  4. 任意更改手办之间的移动顺序不会影响结果。先移动手办1和先移手办3对结果是没有任何影响的,甚至先讲手办1移动1m再将手办3移动2m再将手办1移动3m也是不会对结果造成影响的
  5. 总移动次数永远不变。假设有10个手办一排,你会发现不管是以哪个位置为中心移动,最后的总移动次数都是1+2+3+…+9=45次(注意这里是指45次一米的移动操作,详见2)。参考3,由于手办可以合并成一个手办,这样此实际移动次数并不需要45次,而是只需要9次(想一想为什么),接下来题目中我们也是按照后者更少的移动方式来进行。

接下来我们假设一排有10个手办
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ <-手办
1 2 5 3 2 4 3 4 2 2 <-权值
根据结论4,我们每次可以将问题简化为:
有一堆手办,每次可以将最左的手办向右移动或者将最右的手办向左移动,问最终手办合成一堆后所做的功最少是多少?
接下来我们就解决这个等价问题即可。
根据5可知,在进行9次操作后,我们的手办就合并成一堆了。那我们是不是只要找到做功最小的9次操作就可以了。
首先我们放眼望去,最小的操作是哪个?
很显然是将第一个手办和第二个手办合并,只需要做1w的功。(这个是所有操作里做功最小的操作)
后并后就是这样
■ ■ ■ ■ ■ ■ ■ ■ ■ <-手办
3 5 3 2 4 3 4 2 2 <-权值
现在最小的呢?
其实也很显然,是最右边两个手办合并,最终做了2w的功。(这个是所有操作里做功第二小的操作)
为什么?
我们知道手办是越合并越大的,到后面合并做的功只会变大不会变少,所以左右两边的操作肯定有一个是当前最小的。所以当前最优的操作其实就是全局最优的。符合贪心准则里的:局部最优推全局最优。所以这个贪心方法是正确的。也就是当前左右两个手办哪个权值小我就合并哪一边。

代码实现

import java.util.Scanner;

public class Main2
{
    public static void main(String[] args) {
        Scanner scanner =new Scanner(System.in);
        int n=scanner.nextInt();//有n个手办
        int[] handDo=new int[n];//存手办权值
        for(int i=0;i<n;i++){
            handDo[i]=scanner.nextInt();
        }
        int l=0,r=n-1;
        int work=0;//做功
        while (l!=r){//l!=r说明还没合并成一堆,需要继续合并
            if(handDo[l]<handDo[r]){//左右两个哪个权值小就合并哪个
                handDo[l+1]+=handDo[l];//更新权值
                work+=handDo[l];
                l++;
            }else {
                handDo[r-1]+=handDo[r];//更新权值
                work+=handDo[r];
                r--;
            }
        }
        System.out.println(work);
    }
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-05-21 19:13:41  更:2022-05-21 19:16:15 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 19:37:33-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码