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;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【LeetCode刷题-树】--1367.二叉树中的链表

1367.二叉树中的链表 方法&#xff1a;枚举 枚举二叉树中的每个节点为起点往下的路径是否与链表相匹配的路径&#xff0c;为了判断是否匹配设计了一个递归函数dfs(root,head),其中root表示当前匹配到的二叉树节点&#xff0c;head表示当前匹配到的链表节点&#xff0c;整个函数…

opencv(2): 视频采集和录制

视频采集 相关API VideoCapture()cap.read()&#xff1a; 返回两个值&#xff0c;第一个参数&#xff0c;如果读到frame&#xff0c;返回 True. 第二个参数为相应的图像帧。cap.release() VideoCapture cv2.VideoCapture(0) 0 表示自动检测&#xff0c;如果在笔记本上运行&…

微服务和Spring Cloud Alibaba介绍

1、微服务介绍 1.1 系统架构演变 随着互联网的发展&#xff0c;网站应用的规模也在不断的扩大&#xff0c;进而导致系统架构也在不断的进行变化。从互联网早起到现在&#xff0c;系统架构大体经历了下面几个过程: 单体应用架构 —> 垂直应用架构 —> 分布 式架构—>…

Selenium操作已经打开的Chrome浏览器窗口

Selenium操作已经打开的Chrome浏览器窗口 0. 背景 在使用之前的代码通过selenium操作Chrome浏览器时&#xff0c;每次都要新打开一个窗口&#xff0c;觉得麻烦&#xff0c;所以尝试使用 Selenium 获取已经打开的浏览器窗口&#xff0c;在此记录下过程 本文使用 chrome浏览器来…

springboot引入redisson分布式锁及原理

1.引入依赖 <dependency><groupId>org.redisson</groupId><artifactId>redisson</artifactId><version>3.13.6</version> </dependency>2.配置类创建bean /*** author qujingye* Classname RedissonConfig* Description TOD…

基于单片机的水位检测系统仿真设计

**单片机设计介绍&#xff0c; 基于单片机的水位检测系统仿真设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的水位检测系统仿真系统是一种用于模拟水位检测系统的工作过程&#xff0c;以验证设计方案的可行性和优…

CCRC认证是什么?

什么是CCRC认证&#xff1f; 信息安全服务资质&#xff0c;是信息安全服务机构提供安全服务的一种资格&#xff0c;包括法律地位、资源状况、管理水平、技术能力等方面的要求。 信息安全服务资质&#xff08;CCRC&#xff09;是依据国家法律法规、国家标准、行业标准和技术规范…

系列五、怎么查看默认的垃圾收集器是哪个?

一、怎么查看默认的垃圾收集器是哪个 java -XX:PrintCommandLineFlags -version

main.js 中的 render函数

按照之前的单组件文件中的写法&#xff0c;我们的写法应该是这样的 import App from ./App.vuenew Vue({el: #app,templete: <App></App>,components: {App}, }) 1、定义el根节点。2、注册App组件。3、渲染 templete 模板 但是在脚手架工程中&#xff0c;他是这…

excel中vlookup用法

excel中vlookup用法 用法示例 参数说明 参数1&#xff1a;E1用于匹配的字段 参数2&#xff1a;E1:F4&#xff0c;匹配表格范围 参数3&#xff1a;要取的字段属于匹配表格范围的第几列 数据4&#xff1a;精确匹配

react实现步进器

创建一个步进器组件&#xff0c;包含当前步骤&#xff08;currentStep&#xff09;的状态以及前进和后退的操作&#xff1a; import React, { useState } from react;function Stepper() {const [currentStep, setCurrentStep] useState(1);const handleNext () > {setCu…

python-opencv 培训课程作业

python-opencv 培训课程作业 作业一&#xff1a; 第一步&#xff1a;读取 res 下面的 flower.jpg&#xff0c;读取彩图&#xff0c;并用 opencv 展示 第二步&#xff1a;彩图 -> 灰度图 第三步&#xff1a;反转图像&#xff1a;最大图像灰度值减去原图像&#xff0c;即可得…

2023.11.18 - hadoop之zookeeper分布式协调服务

1.zookeeper简介 ZooKeeper概念: Zookeeper是一个分布式协调服务的开源框架。本质上是一个分布式的小文件存储系统 ZooKeeper作用: 主要用来解决分布式集群中应用系统的一致性问题。 ZooKeeper结构: 采用树形层次结构&#xff0c;没有目录与文件之分,ZooKeeper树中的每个节点被…

linux文件IO

文件IO截断 截断对文件的偏移量没有影响。

Sqlite安装配置及使用

一、下载SQLite Sqlite官网 我下载的是3370000版本:sqlite-dll-win64-x64-3370000.zip 和 sqlite-tools-win32-x86-3370000.zip 二、解压下载的两个压缩包 三、配置环境 四、检查是否安装配置成功 winR&#xff1a;输入cmd调出命令窗口&#xff0c;输入sqlite3后回车查看s…

2023-11-17 VsCode使用makefile进行多文件编译

点击 <C 语言编程核心突破> 快速C语言入门 VsCode使用makefile进行多文件编译 前言一、一个简单的多文件示例二、makefile基本语法三、VsCode使用makefile总结 前言 要解决问题: C或C可以多文件编译, 意味着需要进行代码组织, 为了方便多文件编译, gnu开发了make工具, …

mac苹果笔记本应用程序在哪?有什么快捷方式吗?

苹果笔记本电脑一直以来都被广泛使用&#xff0c;而苹果的操作系统 macOS 也非常受欢迎。一台好的笔记本电脑不仅仅依赖于硬件配置&#xff0c;还需要丰富多样的应用程序来满足用户的需求。苹果笔记本应用程序在哪&#xff0c;不少mac新手用户会有这个疑问。在这篇文章中&#…

PMCW体制雷达系列文章(4) – PMCW雷达之抗干扰

说明 本文作为PMCW体制雷达系列文章之一&#xff0c;主要聊聊FMCW&PMCW两种体制雷达的干扰问题。事实上不管是通信领域还是雷达领域&#xff0c;对于一切以电磁波作为媒介的信息传递活动&#xff0c;干扰是无处不在的。近年来&#xff0c;随着雷达装车率的提高&#xff0c;…

python科研绘图:面积图

目录 1、面积图 2、堆积面积图 1、面积图 面积图是一种数据可视化图表&#xff0c;用于展示数据随时间或其他有序类别的变化趋势。它与折线图相似&#xff0c;但在展示数据变化的同时&#xff0c;面积图还强调了各个数据点之间的累积关系。这种图表通常通过在折线下方填充颜…

HarmonyOS开发:动态共享包的依赖问题

一、共享包的依赖方式 在需要依赖的模块包目录下oh-package.json5文件中添加依赖&#xff1a; "dependencies": {"ohos/srpaasUI": "file:../../srpaasUI","ohos/srbusiness": "file:../../feature/srbusiness"} 引入之后…