信息学奥赛第十节 —— 贪心算法(渡河问题POJ 1700 Crossing River + 拦截导弹的系统数量求解)

本文主要是介绍信息学奥赛第十节 —— 贪心算法(渡河问题POJ 1700 Crossing River + 拦截导弹的系统数量求解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

复习概念

贪心算法又叫贪婪算法,是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,贪心算法不从整体最优上加以考虑,它所做出的是在某种意义上的局部最优解。
无后效性:贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
贪心算法使用的前提:局部最优解一定能导致全局最优解。

贪心算法的过程
  • 建立数学模型来描述问题
  • 把求解的问题分成若干个子问题
  • 对每一子问题求解,得到子问题的局部最优解
  • 把子问题的局部最优解合成原来解问题的一个解
贪心算法之渡河问题 POJ 1700 Crossing River

问题描述

现在有一群人,到了一条河旁边,想要过河,但船只有一条,这条船一次最多能载两个人,开到了对面还需要一个人负责把船开回来,而且若多人坐船,船的速度还是由慢的那个人决定,现在求如何分配坐船,使总时间最短。

输入

输入t组数据,每组数据第1行输入n,第二行输入n个数,表示每人过河的时间

输出

输出t行数据,每行1个数,表示每组过河的最少时间

样例输入

1
4
1 2 5 10

样例输出

17

在这里插入图片描述

贪心策略的选取

  • 策略一:每次选择当前过河速度最快的两个人。首先选择1与2同时过河,总时间为2,然后需要1把船开回来,此时总时间为2+1=3;接着选择1与5同时过河,再用1把船开回来,此时总时间变为3+5+1=9;最后一趟,1与10同时过河,过河时间为10,总时间变为9+10=19。

  • 策略二:每次选择当前过河速度最慢的两个人。首先选择5与10同时过河,总时间为10,然后需要5把船开回来,此时总时间为10+5=15;接着选择2与5同时过河,再用2把船开回来,此时总时间变为15+5+2=22;最后一趟,1与2同时过河,过河时间为2,总时间变为22+2=24。

  • 策略三:每次选择当前过河速度最快和最慢的两个人。首先选择1与10同时过河,总时间为10,然后需要1把船开回来,此时总时间为10+1=11;接着选择1与5同时过河,再用1把船开回来,此时总时间变为11+5+1=17;最后一趟,1与2同时过河,过河时间为2,总时间变为17+2=19。
    在这里插入图片描述

  • 不难发现,以上三种贪心策略均达不到最优解

  • 策略四:先让两个最快的过河,首先选择1与2同时过河,总时间为2,然后需要1把船开回来,此时总时间为2+1=3;接着选择最慢的两个人过河,即5与10同时过河【5、10同时过河与1、10同时过河的时间相同,肯定优先选5、10同时过河】,总时间为3+10=13,再用2把船开回来,此时总时间变为13+2=15;最后一趟,1与2同时过河,过河时间为2,总时间变为15+2=17。
    在这里插入图片描述

解题思路及AC代码

假设现在有k个人还没有渡河,设往返各两次为一轮,则经过一轮之后,渡河人数减少了2。通过上述分析,从策略三与策略四中选最小者,就是本题耗时最少的时间。

  • 对于策略三:每次让最快者带最慢者,最快者再开船返回。
    在这里插入图片描述

  • 对于策略四:先让两个最快者渡河,最快的人开船返回。再让两个最慢者渡河,速度次快的开船返回…
    在这里插入图片描述
    AC代码:

#include <iostream>
#include <algorithm>using namespace std;
const int N = 1010;
int a[N];//存储每个人的渡河时间
int ans;//用来记录所有人渡河的最少总时间
int n;//表示渡河人数int crossRiver_time(int k)//表示此时还有n个人没有渡河
{while (k > 0){if (k == 1) { ans += a[1]; k -= 1; }//只有一个人渡河else if (k == 2) { ans += a[2]; k -=2; }//两个人渡河的时候,渡河时间由较慢者决定:a[2] > a[1]else if (k == 3) { ans += (a[1] + a[2] + a[3]); k -= 3; }else{int t1 = 2 * a[1] + a[k] + a[k - 1];//策略三int t2 = a[1] + 2 * a[2] + a[k];//策略四int t = min(t1,t2);//取策略三、四的最小者ans += t;k -= 2;//经过一轮渡河之后,岸边需要渡河的人数减少2}}return ans;
}int main()
{int t; cin >> t;//组数while (t --){ans = 0;//多组输入,重置anscin >> n;//人数for (int i = 1;i <= n;i++) cin >> a[i];//渡河时间sort(a + 1,a + n + 1);//从小到大排序ans = crossRiver_time(n);cout << ans << endl;}return 0;
}
贪心练习2 原题链接

题目描述

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。假设某天雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。 输入n个导弹依次飞来的高度(给出的高度数据是不大于30000的正整数),计算如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 比如:有8颗导弹,飞来的高度分别为389 207 175 300 299 170 158 165 。那么需要2个系统来拦截,他们能够拦截的导弹最优解分别是:
系统1:拦截 389 207 175 170 158
系统2:拦截 300 299 165

输入

两行,第一行表示飞来导弹的数量n(n<=1000)
第二行表示n颗依次飞来的导弹高度

输出

要拦截所有导弹最小配备的系统数k

样例输入

8
389 207 175 300 299 170 158 165

样例输出

2

作业题:拦截导弹方案求解

这篇关于信息学奥赛第十节 —— 贪心算法(渡河问题POJ 1700 Crossing River + 拦截导弹的系统数量求解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/591552

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务,目标是自动识别图像中的对象类别。通过卷积神经网络(CNN)等深度学习技术,我们可以构建高效的图像分类系统,广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统,包括环境

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

嵌入式QT开发:构建高效智能的嵌入式系统

摘要: 本文深入探讨了嵌入式 QT 相关的各个方面。从 QT 框架的基础架构和核心概念出发,详细阐述了其在嵌入式环境中的优势与特点。文中分析了嵌入式 QT 的开发环境搭建过程,包括交叉编译工具链的配置等关键步骤。进一步探讨了嵌入式 QT 的界面设计与开发,涵盖了从基本控件的使用到复杂界面布局的构建。同时也深入研究了信号与槽机制在嵌入式系统中的应用,以及嵌入式 QT 与硬件设备的交互,包括输入输出设

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听