贪心算法:多处最优服务次序、删数问题
多处最优服务次序问题
问题描述:设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti(1≤i≤n),共有s处可以提供此项服务。应如何安排n个顾客的服务次序,才能使平均等待时间达到最小?平均等待时间是n个顾客等待服务时间的总和除以n。
算法设计:对于给定的n个顾客需要的服务时间和s的值,计算最优服务次序。
数据输入:由文件input.txt给出输入数据。第1行有2个正整数n和s,表示有n个顾客且有s处可以提供顾客需要的服务。接下来的1行中有n个正整数,表示n个顾客需要的服务时间。
结果输出:将计算的最小平均等待时间输出到文件output.txt。
输入文件示例input.txt
10 2
56 12 1 99 1000 234 33 55 99 812
输出文件示例output.txt
336
思路分析:
- 贪心算法:优先安排服务时间较短的顾客,减少其他顾客的等待时间
- 多窗口调度:将顾客分配到当前累计等待时间最少的窗口
- 平均等待时间计算:所有顾客等待时间的总和除以顾客数量
具体步骤:
- 将顾客按服务时间从短到长排序
- 初始化s个服务窗口,每个窗口的累计服务时间为0
- 对于每个顾客,将其分配到当前累计服务时间最少的窗口
- 将该顾客的服务时间加到该窗口的累计服务时间中
- 将该顾客的等待时间(即分配前的窗口累计服务时间)加入总等待时间
- 最后计算平均等待时间
调试分析:
- 调试时VS Code默认的工作目录是项目根目录(D:\myvscode),因此用相对路径打开input.txt会显示文件打开失败,此时可以将文件路径切换为绝对路径。
- /:整除,向下取整,不会四舍五入,截断掉了小数部分,向零取整。
- 题目中的“等待时间”是指顾客从开始等到服务结束的总时间。即:等待时间 = 开始服务时间 + 自己的服务时间。
total_waiting_time += windows[min_idx];应改为:
total_waiting_time += windows[min_idx] + serve_time[i];
#include <stdio.h>
#include <stdlib.h>//比较函数,用于排序
int compare(const void *a,const void *b){return (*(int *)a - *(int *)b);
}int main(){int n, s, total = 0;/*在 VS Code 中调试时,默认的工作目录是项目根目录(D:\myvscode)FILE *inputFile = fopen("input.txt", "r");FILE *outputFile = fopen("output.txt", "w");*/FILE *inputFile = fopen("D:/myvscode/daer2_suanfa/input.txt", "r");FILE *outputFile = fopen("D:/myvscode/daer2_suanfa/output.txt", "w");if(inputFile == NULL || outputFile == NULL){printf("文件打开失败!\n");return 1;}fscanf(inputFile, "%d %d", &n, &s);//读取服务时间int *serve_time = (int *)malloc(n * sizeof(int));for (int i = 0; i < n;i++){fscanf(inputFile, "%d", &serve_time[i]);}fclose(inputFile);//将服务时间按升序排序qsort(serve_time, n, sizeof(int), compare);//创建一个数组来存储每个窗口的服务时间int *windows = (int *)malloc(s * sizeof(int));for (int i = 0; i < s; i++) {windows[i] = 0; // 初始化每个窗口的结束时间}//遍历每个顾客for (int i = 0; i < n;i++){int min_window = 0;for (int j = 0; j < s;j++){ //遍历每个窗口找最短服务时间的窗口if(windows[j]<windows[min_window]){min_window = j;}}total += windows[min_window] + serve_time[i];//增加等待时间windows[min_window] += serve_time[i];//更新窗口时间}int average = total / n;fprintf(outputFile, "%d\n", average);fclose(outputFile);free(serve_time);//释放内存free(windows);return 0;
}
删数问题
问题描述:给定n位正整数a,去掉其中任意k≤n个数字后,剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k,设计一个算法找出剩下数字组成的新数最小的删数方案。
算法设计:对于给定的正整数a,计算删去k个数字后得到的最小数。
数据输入:由文件input.txt提供输入数据。文件的第1行是1个正整数a。第2行是正整数k。
结果输出:将计算的最小数输出到文件output.txt。
输入文件示例
input.txt
178543
4
输出文件示例
output.txt
13
思路分析:
- 贪心策略:
从左到右遍历数字,如果当前数字比下一个数字大,就删除当前数字(因为这样可以让后面的更小的数字前移)。
重复这个过程 k 次,直到删除 k 个数字。
特殊情况:
如果数字已经是升序(如 12345),直接删除最后 k 位。
如果 k 次删除未完成,但已经无法找到更大的数字(如 1111),直接删除末尾剩余的数字。
- 实现方法:
使用 栈(Stack) 来模拟删除过程:
1.遍历数字的每一位。
2.如果当前数字比栈顶的数字小,并且还可以删除(k > 0),就弹出栈顶数字(相当于删除),并减少 k。
3.否则,将当前数字压入栈。
4.如果遍历完成后 k 仍然大于 0,则从末尾删除剩余 k 个数字。
调试分析:
- 遍历数字 O(n),每个数字最多入栈和出栈一次,因此总时间复杂度为 O(n)。
- 边界情况:
k = 0
:直接返回原数字。k = n
:返回0
。- 数字有前导
0
(如1001
删除2
位后得到00
,应输出0
)。
- 特别注意 前导零 和 剩余
k
未删完 的情况。可以使用printf
打印中间变量(栈状态)调试。 - 前导0问题:例如,输入10200,删除1位后得到0200,应表示200。设置start指针循环检查。
- 重定向
重定向 是指改变程序默认的输入/输出(I/O)方向。通常:
- 标准输入(stdin):默认是键盘输入。
- 标准输出(stdout):默认是屏幕(控制台)输出。
- 标准错误(stderr):默认也是屏幕输出。
重定向的作用:
- 把程序的输出从屏幕 重定向 到文件(如 output.txt)。
- 也可以把文件的输入 重定向 到程序(如从 input.txt 读取数据)。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void removeK(char *num,int k){int n = strlen(num);if(k>=n){printf("0\n");return;}char *stack = (char *)malloc((n + 1) * sizeof(char));int top = -1;//栈顶指针for (int i = 0; i < n;i++){while(top>=0 && num[i]<stack[top] && k>0){top--;k--;}stack[++top] = num[i];//压入当前数字}top -= k;//top-k=top,如果还有剩余的k,从末尾删除//处理前导0int start = 0;//表示stack起始位置while(stack[start]=='0' && start<=top){//循环检查stack开头是否是 '0'start++;}//输出结果if(start>top){printf("0");//如果全部是0,输出0}else{for (int i = start; i <= top;i++){printf("%c", stack[i]);//否则输出非前导0部分}}printf("\n");free(stack);
}
int main(){FILE *inputFile = fopen("input.txt", "r");FILE *outputFile = fopen("output.txt", "w");if (inputFile == NULL || outputFile == NULL){printf("文件打开失败!\n");return 1;}char num[10000];int k;fscanf(inputFile, "%s", num);fscanf(inputFile, "%d", &k);fclose(inputFile);removeK(num, k);//由于 removeK 直接打印,可以重定向到文件freopen("output.txt", "w", stdout);//将标准输出重定向到文件 output.txtremoveK(num, k);//调用函数,所有 printf 都写入文件fclose(outputFile);return 0;
}
相关文章:
贪心算法:多处最优服务次序、删数问题
多处最优服务次序问题 问题描述:设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti(1≤i≤n),共有s处可以提供此项服务。应如何安排n个顾客的服务次序,才能使平均等待时间达到最小?平均等待时间是n个顾客等待服务时间的总和除以n。 算法设计:对于给定的n个顾…...
使用 Flask 框架实现FTP,允许用户通过 Web 界面浏览和下载文件夹中的所有文件
Flask 文件和文件夹下载服务实现 以下是一个基于 Flask 框架的简单 Web 服务,用于开放指定文件夹(./shared_files),允许用户通过浏览器浏览和下载文件夹中的所有文件和子文件夹。ZIP 和 TAR 文件将直接下载,而文件夹将…...
【Go】从0开始学习Go
文章目录 从0开始学习Go0 与C对比1 代码框架1.1 helloworld式代码示例1.2 主体代码元素(核心三部分)1.3 其他 2 与C/C区别3 有用的小工具4 注意事项 从0开始学习Go 0 与C对比 特性CGo编译型语言需要编译为机器码直接编译为二进制可执行文件静态类型类型…...
软件设计师SQL考点分析——求三连
一、考点分值占比与趋势分析 综合知识分值统计表(75分制) 年份考题数量分值分值占比考察重点2018334%关系代数、权限控制2019222.67%SQL注入、授权语句2020445.33%投影操作、权限回收2021334%视图操作、权限传递2022222.67%数据库安全、WITH GRANT OPT…...
使用tcs34725传感器和51单片机识别颜色
使用TCS34725颜色传感器和51单片机来识别颜色是一个非常有趣的项目。TCS34725是一种常用的RGB颜色传感器,能够测量红、绿、蓝光的强度,从而实现颜色识别。 1. 硬件连接 TCS34725传感器通过IC接口与51单片机连接。以下是连接方式: SDA&…...
数据库-oracle-包-视图传参
并发下可能不准确 -- 修改包规范 CREATE OR REPLACE PACKAGE sczz.p_view_param IS function set_n(n varchar2) return varchar2; function get_n return varchar2; function set_ny(ny varchar2) return varchar2; function get_ny return varchar2; …...
深入探讨Java中的上下文传递与ThreadLocal的局限性及Scoped Values的兴起
在Java开发中,特别是在依赖框架的应用程序中,上下文数据的管理是一个常见但具有挑战性的问题。上下文数据可能包括元数据、配置信息或其他需要在代码不同部分之间共享的信息。传统的做法是通过方法参数显式传递这些上下文,但这种方法会导致代码复杂、难以维护,尤其是在大型…...
Spring boot 学习笔记2
Maven 项目管理工具:Maven 通过 pom.xml(Project Object Model)文件描述项目配置,包括依赖、构建流程、插件等,实现项目标准化管理 依赖管理:自动下载并管理项目所需的第三方库(如 Spring、MyB…...
“保证医疗器械信息来源合法 真实、安全的保障措施、情况说明及相关证明”模板
保证医疗器械信息来源合法真实、安全的保障措施、情况说明及相关证明 一、医疗器械信息来源合法、真实、安全的管理措施 目前我公司网站所展示的医疗器械是企业代理品种,是取得合法注册资格的产品,拥有合法证明文件的产品。本网站仅展示本公司行政许可…...
Feature Toggle 不再乱:如何设计一个干净、安全、可控的特性开关系统?
网罗开发 (小红书、快手、视频号同名) 大家好,我是 展菲,目前在上市企业从事人工智能项目研发管理工作,平时热衷于分享各种编程领域的软硬技能知识以及前沿技术,包括iOS、前端、Harmony OS、Java、Python等…...
不锈钢保温容器行业2025数据分析报告
不锈钢保温容器市场概况 2024年全球不锈钢保温容器市场规模约为453.3亿元,预计到2031年将增长至608.3亿元,年均复合增长率(CAGR)为4.3%。这一增长主要得益于全球范围内对保温容器需求的持续增加,尤其是在户外活动、餐…...
leetcode239 滑动窗口最大值deque方式
这段文字描述的是使用单调队列(Monotonic Queue) 解决滑动窗口最大值问题的优化算法。我来简单解释一下: 核心思路 问题分析:在滑动窗口中,若存在两个下标 i < j 且 nums[i] ≤ nums[j],则 nums[i] 永远…...
腾讯云怎么在游戏云中助力
腾讯云游戏云:依托深厚游戏基因,打造高质量全方位生态平台 在竞争激烈的云计算市场中,腾讯云凭借其得天独厚的游戏生态资源和深耕多年的技术沉淀,正成为游戏行业不可忽视的重要力量。腾讯不仅是全球领先的游戏开发和发行商&#…...
深入理解pip:Python包管理的核心工具与实战指南
# 深入理解pip:Python包管理的核心工具与实战指南 在Python开发中,第三方库是提升效率的关键。而pip作为Python官方的包管理工具,承担着安装、卸载、升级和管理库的重要职责。本文将全面解析pip的核心命令,结合实例演示用法&#…...
【python】windows修改 pip 默认安装路径
在 Windows 系统 下,希望修改 pip 默认安装路径,结合你前面贴的图片和信息,一个 推荐做法(不修改 site.py)的完整教程。 目标:让 pip 安装包默认装到你指定的路径(如 D:\MyPythonLibsÿ…...
Python函数——万字详解
—— 小 峰 编 程 导 语: 从今天开始,我们将进入第二模块的学习——函数。第一模块主要是学习python基础知识,从第二模块开始就可以通过程序去解决工作中实际的问题。从今天开始,我们将进入第二模块的学习,此模块…...
es在已有历史数据的文档新增加字段操作
新增字段设置默认值 场景 在已经有大量数据的索引文档上,增加新字段 技术实现 一.更新索引映射 通过PUT请求显式定义新字段类型,确保后续写入的文档能被正确解析 PUT /文档名/_mapping {"properties": {"字段名1": {"type…...
LeetCode 35 搜索插入位置题解
LeetCode 35 搜索插入位置题解 题目描述 题目链接 给定一个排序数组和一个目标值,在数组中找到目标值并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置(需保证数组仍然有序)。要求时间复杂度为 O(log n)。…...
RabbitMQ通信模式(Simplest)Python示例
RabbitMQ通信模式-Python示例 0.RabbitMQ官网通信模式1.Simplest(简单)模式1.1 发送端1.2 接收端 0.RabbitMQ官网通信模式 1.Simplest(简单)模式 1.1 发送端 # -*- coding: utf-8 -*- """ Author: xxx date: 2025/5/19 11:30 Description: Simaple简单模…...
游戏开发实战(一):Python复刻「崩坏星穹铁道」嗷呜嗷呜事务所---源码级解析该小游戏背后的算法与设计模式【纯原创】
文章目录 奇美拉项目游戏规则奇美拉(Chimeras)档案领队成员 结果展示: 奇美拉项目 由于项目工程较大,并且我打算把我的思考过程和实现过程中踩过的坑都分享一下,因此会分3-4篇博文详细讲解本项目。本文首先介绍下游戏规则并给出奇美拉档案。…...
力扣热题100之删除链表的倒数第N个节点
题目 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 代码 方法一 将链表中的值放入列表中,然后删除倒数第n个值,再将剩下的数依次转化为链表 # Definition for singly-linked list. # class ListNode: # …...
OCframework编译Swift
建一个OC的framework: 需要对外暴露的OC文件,需要放到OC的.h文件中 framework中,OC类,调用framework中的Swift类: #import "WowAudioFocus/WowAudioFocus-Swift.h" //02 #import "{工程名}/{工程…...
【AI News | 20250519】每日AI进展
AI Repos 1、deepdrone DeepDrone是一款基于smolagents框架的无人机聊天代理,集成DroneKit实现无人机分析与操作。用户可通过自然语言聊天与无人机助手交互,实现飞行路径和传感器数据可视化、基于飞行时长的维护建议、任务规划以及真实的无人机控制&…...
分布式ID生成系统
代码地址: github mid 简介 分布式 ID 生成系统是一个高性能、可靠的 ID 生成服务,支持两种模式:Snowflake(基于时间戳的内存生成)和 Segment(基于 MySQL 的号段分配)。系统采用双 Buffer 策略优化性能,集成 Prometheus 监控和 Zap 结构化日志,确保高可用性和可观测性…...
MAC常用操作整理
音量方法: 电脑键盘的右上角就有静音和不静音的按钮,还有调节音量的按钮,调节屏幕亮度的按钮 切换输入法方法: 1.大写按键,2.function按键(fn), 3.control 空格键, 选择上一个输入法,4.controloption空格…...
【Canvas与图标】圆角方块蓝星CSS图标
【成图】 120*120的png图标 大小图: 【代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"/> <head><title>圆角方块蓝星CSS Draft1</…...
易境通散货拼柜系统:提高货代企业货物配载效率
在国际物流代理运输领域,货物配载是整个供应链的核心环节,其优化对于提升整个供应链的效率至关重要。传统的配载管理方式往往依赖人工操作,不仅效率低下,还容易出现错误。面对多订单、多货主、多目的地的复杂场景,传统…...
[Spring Boot]整合Java Mail实现Outlook发送邮件
日常开发过程中,我们经常需要使用到邮件发送任务,比方说验证码的发送、日常信息的通知等。日常比较常用的邮件发送方包括:163、QQ等,本文主要讲解Outlook SMTP的开启方式、OutLook STARTTTL的配置、如何通过JavaMail来实现电子邮件的发送等。 Outlook作为微软提供的企业电子…...
【盈达科技】GEO优化实战策略
提升内容在生成式引擎中的可见性:实战策略 随着生成式引擎(Generative Engines, GEs)的兴起,内容创作者面临着新的挑战和机遇。这些引擎通过整合和总结多源信息来提供精准且个性化的回答,正在迅速取代传统搜索引擎。为…...
HTTP 协议基础
本篇文章会从如下角度介绍 HTTP 协议: 原理与工作机制请求方法与状态码Header 与 Body 1、原理与工作机制 1.1 HTTP 是什么 HyperText Transfer Protocol,超文本传输协议,"超"表示扩展而非超级,即可以链接到其他文本…...
ros运行包,Ubuntu20.04成功运行LIO-SAM
zz:~/lio_sam_ws$ source devel/setup.bash zz:~/lio_sam_ws$ roslaunch lio_sam run.launch 创建包链接: 链接1:Ubuntu20.04成功运行LIO-SAM_ubuntu20.04运行liosam-CSDN博客 链接2:ubuntu 20.04 ROS 编译和运行 lio-sam,并且导出PCD文件…...
Linux《自主Shell命令行解释器》
在上一篇的进程控制当中我们已经了解了进程退出、进程等待以及进程替换的相关概念,那么在了解了这些的概念之后接下来在本篇当中我们就可以结合之前我们学习的知识来实现一个自主的Shell命令行解释器,通过Shell的实现能让我们进一步的理解操作系统当中的…...
设置IDEA打开新项目使用JDK17
由于最近在学习Spring-AI,所以JDK8已经不适用了,但是每次创建新项目都还是JDK8,每次调来调去很麻烦 把Projects和SDKs都调整为JDK17即可 同时,Maven也要做些更改,主要是添加build标签 <build><plugins>&…...
Vue百日学习计划Day36-42天详细计划-Gemini版
总目标: 在 Day 36-42 理解组件化开发的思想,熟练掌握 Vue 组件的注册、Props、Events、v-model、Slots、Provide/Inject 等核心概念和实践,能够构建可复用和易于维护的组件结构。 所需资源: Vue 3 官方文档 (组件基础): https://cn.vuejs.org/guide/es…...
Python对JSON数据操作
在Python中,对JSON数据进行增删改查及加载保存操作,主要通过内置的json模块实现。 一、基础操作 1. 加载JSON数据 • 从文件加载 使用json.load()读取JSON文件并转换为Python对象(字典/列表): import json with open…...
upload靶场1-5关
网上的解析有一些题目对应不上,比如第五关说是 空格 点 空格绕过 ,我这里就无法成功解析,但大小写绕过就成功了,慢慢会把后面的关卡也写出来 这里建议开一台win7的虚拟机,在上面搭建靶场,可以省很多麻烦 …...
网络传输(ping命令,wget命令,curl命令),端口
网络传输: ping命令:检查指定的网络服务器是否是可联通状态 语法:ping 【-c num】IP或主机名 -c:是检查的次数,不使用-c,将无限次持续检查 wget命令:wget是非交互式的文件下载器࿰…...
upload-labs靶场通关详解:第10关
一、分析源代码 $is_upload false; $msg null; if (isset($_POST[submit])) {if (file_exists(UPLOAD_PATH)) {$deny_ext array(".php",".php5",".php4",".php3",".php2",".html",".htm",".ph…...
深入解析`lsof`命令:查看系统中打开文件与进程信息
1、lsof的基本概念 lsof (List Open Files) 提供了一种方式来查看系统上哪些进程正在访问哪些文件,能够显示文件类型、文件名、文件描述符、所属进程等详细信息。 在类Unix系统中,几乎所有的操作都与文件相关联,文件不…...
C++ 与 Python 内存分配策略对比
内存管理是编程中的一个核心概念,它直接影响程序的性能、稳定性和资源利用率。C 和 Python 作为两种广泛使用的编程语言,在内存分配和管理方面采用了截然不同的策略。 C 内存分配策略 C 赋予程序员对内存的精细控制能力,同时也带来了更大的…...
TB开拓者策略交易信号闪烁根因及解决方法
TB开拓者策略信号闪烁分析 TB开拓者策略交易信号闪烁根因 TB开拓者策略交易信号闪烁根因分析 信号闪烁是交易策略开发中常见的问题,特别是在TB(TradeBlazer)开拓者等平台上。以下是信号闪烁的主要根因分析: 主要根因 未来函数问题 使用了包含未来信息…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(24):受身形
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(24):受身形 1、前言(1)情况说明(2)工程师的信仰2、知识点(1)うけみけい 受身形(2)復習(ふくしゅう):3、单词(1)日语(2)日语片假名单词4、相近词练习5、单词辨析记录6、总结1、前言 (1)情况说明 自己在今…...
牛客网NC209794:使徒袭来
牛客网NC209794:使徒袭来 题目背景 问题分析 数学建模 设三位驾驶员的战斗力分别为 a, b, c已知条件:a b c n (n为输入的正整数)目标:求 a b c 的最小值 解题思路 根据算术-几何平均值不等式(AM-GM不等式),对于任意正实数a, b, c&a…...
命令行登录 MySQL 报 Segmentation fault 故障解决
问题描述:对 mysql8.0.35 源码进行 make,由于一开始因为yum源问题少安装依赖库 库,在链接时遇到错误 undefined reference to,后来安装了相关依赖库,再次 make 成功。于是将 mysqld 启动,再用 mysql -u roo…...
2025ICPC邀请赛南昌游记
滚榜时候队伍照片放的人家的闹麻了,手机举了半天 。 最后银牌700小几十罚时,rank60多点。 参赛体验还行,队长是福建人,说感觉这个热度是主场作战哈哈哈哈。空调制冷确实不太行吧。 9s过A是啥,没见过,虽然…...
kotlin flow的写法
以下是 Android 开发中 Kotlin Flow 的常见使用模式和操作符的完整中文总结: 1. 基本 Flow 创建方式 // 从多个值创建 val flow1 flowOf(1, 2, 3)// 使用 flow 构建器 val flow2 flow {emit(1)delay(100)emit(2) }// 从集合创建 val flow3 listOf(1, 2, 3).asFl…...
springboot+mybatis或mybatisplus在进行%name%的前后模糊查询时如何放防止sql注入
在使用 Spring Boot 配合 MyBatis 或 MyBatis-Plus 进行数据库操作时,确保防止 SQL 注入是非常重要的。对于 %name% 样式的前后模糊查询,以下是几种有效的方法来防止 SQL 注入: 1. 使用 MyBatis 的 <if> 标签和 #{} 占位符 MyBatis 默…...
基于51单片机教室红外计数灯光控制—可蓝牙控制
基于51单片机智能教室灯光 (仿真+程序+原理图+PCB+设计报告) 功能介绍 具体功能: 本系统由STC89C52单片机时钟芯片DS1302液晶屏LCD1602光敏电阻红外对管LED灯模块按键模块蓝牙模块构成 具体…...
HTTPS、SSL证书是啥?网站“安全小锁”的入门科普
你有没有发现,浏览网页时,有些网站地址栏前面会出现一个小锁的图标🔒,而有些网站却没有?这个小锁其实代表着网站用了“HTTPS”,是比普通“HTTP”更安全的协议。今天,我们就来聊聊HTTPS、SSL证书…...
大模型备案中的安全考量:筑牢数字时代的安全防线
在数字化浪潮席卷全球的当下,大模型技术凭借强大的数据分析、模式识别与语言理解生成能力,成为推动产业变革、提升社会运转效率的关键力量。从智能客服降本增效,到医疗影像精准诊断,再到金融风险智能预测,大模型正重塑…...