SDUT OJ《算法分析与设计》贪心算法
A - 汽车加油问题
Description
一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。并证明算法能产生一个最优解。
对于给定的n和k个加油站位置,计算最少加油次数。
Input
输入数据的第一行有2 个正整数n和k(n≤5000,k≤1000),表示汽车加满油后可行驶n公里,且旅途中有k个加油站。接下来的1 行中,有k+1 个整数,表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地,汽车已加满油。第k+1 个加油站表示目的地。
Output
将计算出的最少加油次数输出。如果无法到达目的地,则输出“No Solution!”。
Samples
Sample #1
Input
Output
7 7 1 2 3 4 5 1 6 6
4
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N];
//0 1 1 1 1 1 1 1 0
// 1 5 4 5 4 3 3 3
int main()
{int n, k;int cnt = 0;bool flag = 0;cin >> n >> k;for(int i = 0; i <= k; i++){cin >> a[i];if(a[i] > n){flag = 1;}}int d = n;if(flag) cout << "No Solution!" << "\n";else{for(int i = 0; i <= k; i++){if(d >= a[i]){d -= a[i];}else{d = n;cnt++;d -= a[i];}}cout << cnt << "\n";}return 0;
}
B - 多元Huffman编码问题
Description
在一个操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次至少选2 堆最多选k堆石子合并成新的一堆,合并的费用为新的一堆的石子数。试设计一个算法,计算出将n堆石子合并成一堆的最大总费用和最小总费用。
对于给定n堆石子,计算合并成一堆的最大总费用和最小总费用。
Input
输入数据的第1 行有2 个正整数n和k(n≤100000,k≤10000),表示有n堆石子,每次至少选2 堆最多选k堆石子合并。第2 行有n个数(每个数均不超过 100),分别表示每堆石子的个数。
Output
将计算出的最大总费用和最小总费用输出,两个整数之间用空格分开。
Samples
Sample #1
Input
Output
7 3 45 13 12 16 9 5 22
593 199
Hint
请注意数据范围是否可能爆 int。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{int n, k;cin >> n >> k;priority_queue<int, vector<int>, greater<int> >q1;priority_queue<int> q2;for(int i = 0; i < n; i++){int x;cin >> x;q1.push(x);q2.push(x);}LL sum1 = 0, sum2 = 0;while(q1.size() % (k-1) != 1){q1.push(0);}while(q1.size() > 1){LL sum = 0;for(int i = 0; i < k; i++){sum += q1.top();q1.pop();}sum1 += sum;q1.push(sum);}while(q2.size() > 1){LL sum = 0;int a = q2.top();q2.pop();int b = q2.top();q2.pop();sum += (a + b);sum2 += sum;q2.push(sum);}cout << sum2 << " " << sum1 << "\n";return 0;
}
C - 装船问题
Description
王小二毕业后从事船运规划工作,吉祥号货轮的最大载重量为M吨,有10种货物可以装船。第i种货物有wi吨,总价值是pi。王小二的任务是从10种货物中挑选若干吨上船,在满足货物总重量小于等于M的前提下,运走的货物的价重比最大。
Input
输入数据的第一行有一个正整数M(0 < M < 10000),表示所有货物最大载重量。在接下来的10行中,每行有若干个数(中间用空格分开),第i行表示的是第i种货物的货物的总价值pi ,总重量wi。(pi是wi的整数倍,0 < pi , wi < 1000)
Output
输出一个整数,表示可以得到的最大价值。
Samples
Sample #1
Input
Output
100 10 10 20 10 30 10 40 10 50 10 60 10 70 10 80 10 90 10 100 10
550
Hint
价重比:计算其价值与重量之比
#include<bits/stdc++.h>
using namespace std;
const int N = 12;
int p[N], w[N], c[N];
int main()
{int m;cin >> m;for(int i = 0; i < 10; i++){cin >> p[i] >> w[i];c[i] = p[i] / w[i];}for(int i = 0; i < 9; i++){for(int j = i; j < 10; j++){if(c[i] < c[j]){int t = p[i];p[i] = p[j];p[j] = t;t = w[i];w[i] = w[j];w[j] = t;t = c[i];c[i] = c[j];c[j] = t;}}}int sum = 0;for(int i = 0; i < 10; i++){if(m >= w[i]){m -= w[i];sum += p[i];}else{sum += c[i] * m;break;}}cout << sum << "\n";return 0;
}
D - 活动选择
Description
学校的大学生艺术中心周日将面向全校各个学院的学生社团开放,但活动中心同时只能供一个社团活动使用,并且每一个社团活动开始后都不能中断。现在各个社团都提交了他们使用该中心的活动计划(即活动的开始时刻和截止时刻)。请设计一个算法来找到一个最佳的分配序列,以能够在大学生艺术中心安排不冲突的尽可能多的社团活动。
比如有5个活动,开始与截止时刻分别为:

最佳安排序列为:1,4,5。
Input
第一行输入活动数目n(0<n<100);
以后输入n行,分别输入序号为1到n的活动使用中心的开始时刻a与截止时刻b(a,b为整数且0<=a,b<24,a,b输入以空格分隔)。
Output
输出最佳安排序列所包含的各个活动(按照活动被安排的次序,两个活动之间用逗号分隔),如果有多个活动安排序列符合要求输出字典序最小的序列。
Samples
Sample #1
Input
Output
6 8 10 9 16 11 16 14 15 10 14 7 11
1,5,4
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
struct activity
{int num;int start;int endd;int flag;
}act[N], t;
int main()
{int n;cin >> n;for(int i = 0; i < n; i++){act[i].num = i + 1;cin >> act[i].start >> act[i].endd;act[i].flag = 0;}for(int i = 0; i < n - 1; i++){for(int j = 0; j < n - 1 - i; j++){if(act[j].endd > act[j+1].endd){t = act[j];act[j] = act[j+1];act[j+1] = t;}}}int s = 0;for(int i = 0; i < n; i++){if(act[i].start >= s){act[i].flag = 1;s = act[i].endd;}}printf("%d", act[0].num);for(int i = 1; i < n; i++){if(act[i].flag == 1){printf(",%d", act[i].num);}}printf("\n");return 0;
}
E - 最优合并问题
Description
给定k 个排好序的序列s1 , s2,……, sk , 用2 路合并算法将这k 个序列合并成一个序列。假设所采用的2 路合并算法合并2 个长度分别为m和n的序列需要m + n -1次比较。试设计一个算法确定合并这个序列的最优合并顺序,使所需的总比较次数最少。
为了进行比较,还需要确定合并这个序列的最差合并顺序,使所需的总比较次数最多。
对于给定的k个待合并序列,计算最多比较次数和最少比较次数合并方案。
Input
输入数据的第一行有1 个正整数k(k≤1000),表示有k个待合并序列。接下来的1 行中,有k个正整数,表示k个待合并序列的长度。
Output
输出两个整数,中间用空格隔开,表示计算出的最多比较次数和最少比较次数。
Samples
Sample #1
Input
Output
4 5 12 11 2
78 52
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N], b[N];
bool cmp(int a, int b){return a > b;
}
int main()
{int k;cin >> k;for(int i = 0; i < k; i++){cin >> a[i];b[i] = a[i];}sort(a, a + k);// 默认降序sort(b, b + k, cmp);// 升序int maxn = 0, minn = 0;for(int i = 0; i < k - 1; i++){a[i+1] = a[i] + a[i+1];minn += a[i+1];sort(a+i+1, a+k);b[i+1] = b[i]+b[i+1];maxn += b[i+1];sort(b+i+1, b+k, cmp);}cout << maxn - k + 1 << " " << minn - k + 1 << "\n";return 0;
}
相关文章:
SDUT OJ《算法分析与设计》贪心算法
A - 汽车加油问题 Description 一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。并证明算法能产生一个最优解。 对于给定的n和k个加油站位置,计算最少加油次数。 I…...
金融业务系统: Service Mesh用于安全微服务集成
随着云计算的不断演进,微服务架构变得日益复杂。为了有效地管理这种复杂性,人们开始采用服务网格。在本文中,我们将解释什么是Service Mesh,为什么它对现代云架构至关重要,以及它是如何解决开发人员今天面临的一些最紧…...
Linux下快速确定目标服务器支持哪些协议和密码套件
实现原理是利用TLS协议的特点和握手过程来进行测试和解析响应来确定目标服务器支持哪些TLS协议和密码套件。 在TLS握手过程中,客户端和服务器会协商并使用相同的TLS协议版本和密码套件来进行通信。通过发送特定的握手请求并分析响应,可以确定目标服务器…...
LeetCode100122. Separate Black and White Balls
文章目录 一、题目二、题解 一、题目 There are n balls on a table, each ball has a color black or white. You are given a 0-indexed binary string s of length n, where 1 and 0 represent black and white balls, respectively. In each step, you can choose two a…...
系列二十六、idea安装javap -c
一、概述 javap -c是一个能够将.java文件反编译为.class文件的指令,例如我在idea中编写了一个Car.java文件,我想看看这个类被编译后长什么样的,就可以使用该指令进行查看。 二、配置 2.1、 Java Bytecode Decompiler File>Settings>Pl…...
nginx 如何根据IP做限流,以及 nginx 直接返回 json 格式数据
Nginx 限流配置 Nginx是如何限流的。随着业务的扩散,系统并发越来越高时,有三样利器用来保护系统,分别是缓存、降级和限流。 随着业务的扩散,系统并发越来越高时,有三样利器用来保护系统,分别是缓存、降…...
C语言链式栈
stack.h typedef struct Node_s {int data;struct Node_s *pNext; } Node_t, *pNode_t;typedef struct Stack_s {pNode_t pHead;//栈顶指针,指向了链表的第一个结点int size;//栈的元素个数 } Stack_t, *pStack_t;void init(pStack_t pStack); void push(pStack_t …...
【Go入门】 Go的http包详解
【Go入门】 Go的http包详解 前面小节介绍了Go怎么样实现了Web工作模式的一个流程,这一小节,我们将详细地解剖一下http包,看它到底是怎样实现整个过程的。 Go的http有两个核心功能:Conn、ServeMux Conn的goroutine 与我们一般编…...
解决k8s node节点报错: Failed to watch *v1.Secret: unknown
现象: 这个现象是发生在k8s集群证书过期,重新续签证书以后。 记得master节点的/etc/kubernetes/kubelet.conf文件已经复制到node节点了。 但是为什么还是报这个错,然后运行证书检查命令看一下: 看样子是差/etc/kubernetes/pki/…...
日志维护库:loguru
在复杂的项目中,了解程序的运行状态变得至关重要。在这个过程中,日志记录(logging)成为我们追踪、调试和了解代码执行的不可或缺的工具。在python语言中常用logging日志库,但是logging日志库使用相对繁琐,在…...
【Go入门】 Go如何使得Web工作
【Go入门】 Go如何使得Web工作 前面小节介绍了如何通过Go搭建一个Web服务,我们可以看到简单应用一个net/http包就方便的搭建起来了。那么Go在底层到底是怎么做的呢?万变不离其宗,Go的Web服务工作也离不开我们第一小节介绍的Web工作方式。 w…...
汽车虚拟仿真视频数据理解--CLIP模型原理
CLIP模型原理 CLIP的全称是Contrastive Language-Image Pre-Training,中文是对比语言-图像预训练,是一个预训练模型,简称为CLIP。该模型是 OpenAI 在 2021 年发布的,最初用于匹配图像和文本的预训练神经网络模型,这个任…...
【Web】Ctfshow SSTI刷题记录1
目录 ①web361 362-无过滤 ②web363-过滤单双引号 ③web364-过滤单双引号和args ④web365-过滤中括号[]、单双引号、args ⑤web366-过滤单双引号、args、中括号[]、下划线 ⑦web367-过滤单双引号、args、中括号[]、下划线、os ⑧web368-过滤单双引号、args、中括号[]、下…...
【广州华锐互动】VR可视化政务服务为公众提供更直观、形象的政策解读
虚拟现实(VR)技术正在逐渐应用于政务服务领域,为公众提供更加便捷、高效和个性化的服务体验。通过VR眼镜、手机等设备,公众可以在虚拟环境中参观政务服务中心,并根据自己的需求选择不同的办事窗口或事项进行咨询和办理…...
音视频项目—基于FFmpeg和SDL的音视频播放器解析(七)
介绍 在本系列,我打算花大篇幅讲解我的 gitee 项目音视频播放器,在这个项目,您可以学到音视频解封装,解码,SDL渲染相关的知识。您对源代码感兴趣的话,请查看基于FFmpeg和SDL的音视频播放器 如果您不理解本…...
Sql Server 2017主从配置之:发布订阅
使用发布订阅模式搭建Sql Server 2017主从同步,类似事件通知机制,基本可以做到准实时同步,可以同时做到一对多的数据同步。 不过发布订阅模式,只能同时数据,不能同步表结构。在创建发布的时候,需要选择需要…...
聊聊logback的EvaluatorFilter
序 本文主要研究一下logback的EvaluatorFilter EvaluatorFilter ch/qos/logback/core/filter/EvaluatorFilter.java public class EvaluatorFilter<E> extends AbstractMatcherFilter<E> {EventEvaluator<E> evaluator;Overridepublic void start() {if …...
解决vue 部分页面缓存,部分页面不缓存的问题
前端时间项目迭代,其中有个需求 在vue里面,有a.b.c三个页面,要达到的效果是从a页面进去b页面,b页面需要刷新,但若从b页面进入c页面了以后再回到b页面,b页面需要保留之前的值,不做刷新࿱…...
修完这个 Bug 后,MySQL 性能提升了 300%
最近 MySQL 官方在 8.0.35 上修复了一个 bug: 这个 bug 是由 Mark Callaghan 发现的。Mark 早年在 Google MySQL 团队,后来去了 Meta MySQL,也主导了 RocksDB 的开发。 Mark 在 #109595 的 bug report 给出了非常详细的复现步骤 在官方修复后…...
【C/PTA】数组进阶练习(二)
本文结合PTA专项练习带领读者掌握数组,刷题为主注释为辅,在代码中理解思路,其它不做过多叙述。 目录 7-1 字符串逆序7-2 字符串替换7-3 统计字符出现次数7-4 IP地址转换7-1 删除重复字符7-2 说反话-加强版7-3 数组-回文串7-4 数组-无聊的菇菇…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
