MT3020 任务分配

思路:利用二分找到某个时间是满足“k个人可以完成” ,并且时间最小。

因为尽量让后面的人做任务,所以从后往前排任务(倒着分配)。从后往前遍历任务,如果此人加上这个任务超出之前求得的时间,就移到上一个人。


#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4 + 10;
int t, k;
int ti[N];bool check(int u)
{              // u秒可不可以由k个人完成int s = 1; // 记录当前的人int a[N];  // 记录每人任务时间memset(a, 0, sizeof(a));for (int i = 1; i <= t; i++) // 遍历t个任务{if (a[s] + ti[i] > u) // 如果当前时间加上当前任务的时间大于u{s++; // 选下一个人a[s] += ti[i];}elsea[s] += ti[i];}if (s > k){ // 人数>kreturn false;}return true;
}
int c[N][2]; //[每人][起点+终点]
void print(int u)
{ // u为时间// 倒着分配int i = k, temp = 0;for (int j = t; j > 0; j--){if (c[i][1] == 0){ // 结束c[i][1] = j;}if (temp + ti[j] > u) // 时间超出,则换人(从后往前i--){c[i][0] = j + 1;i--;temp = ti[j];c[i][1] = j; // 结束}else{ // 时间未超出temp += ti[j];}}c[i][0] = 1;for (int i = 1; i <= k; i++){if (c[i][0] == 0)cout << 0 << " " << 0 << endl;elsecout << c[i][0] << " " << c[i][1] << endl;}
}
signed main()
{int l = -1, r = 0, ans = 0;cin >> t >> k;for (int i = 1; i <= t; i++){cin >> ti[i];l = max(l, ti[i]);//记录最大时间r += ti[i];//记录总时间}// 二分任务的时间while (l <= r){int mid = (l + r) / 2;if (check(mid)){r = mid - 1;ans = mid;}else{l = mid + 1;}}print(ans);return 0;
}

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

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

相关文章

逐步学习Go-sync.RWMutex(读写锁)-深入理解与实战

概述 在并发编程中&#xff0c;我们经常会遇到多个线程或协程访问共享资源的情况。为了保护这些资源不被同时修改&#xff0c;我们会用到"锁"的概念。 Go中提供了读写锁&#xff1a;sync.RWMutex。 sync.RWMutex是Go语言提供的一个基础同步原语&#xff0c;它是Rea…

Nikon | NEF格式图片批量转换为jpg格式

如何将nikon相机拍的NEF格式图片转换为jpg格式呢&#xff1f; 这里推荐一个在线转换的网址&#xff1a; https://picflow.com/convert/nef-to-jpg 添加图片后&#xff0c;可以批量选择图片&#xff0c;点击转换后即可进行下载

74HC595引脚图时序图工作原理

74HC595和74hc164一样是在单片机系统中常用的芯片之一他的作用就是把串行的信号转为并行的信号&#xff0c;常用在各种数码管以及点阵屏的驱动芯片&#xff0c; 使用74HC595可以节约单片机mcu的io口资源&#xff0c;用3个io就可以控制8个数码管的引脚&#xff0c;他还具有一定的…

[攻防世界]Reversing-x64Elf-100

1.查壳 无壳&#xff0c;ELF文件 2.用IDA64打开 找到关键部分 这里有坑&#xff0c;看清楚v3是长度为3数组&#xff0c;里面放三个字符串 3.脚本解密 v1"Dufhbmf" v2"pGimos" v3"ewUglpt" v4[v1,v2,v3] a1[0,0,0,0,0,0,0,0,0,0,0,0] for i …

乐趣Python——办公魔法:Word文件自动化

嘿&#xff0c;朋友们&#xff01;在这个办公小课堂中&#xff0c;我将为大家揭开一个神奇的秘密&#xff1a;Word文件自动化处理&#xff01; 通过这种魔法般的方式&#xff0c;我们可以大大提高办公效率&#xff0c;减少重复性工作。而Python作为我们的助手&#xff0c;将展现…

JavaSE-12笔记【集合1(+2024新)】

文章目录 1. 集合概述2.Collection2.1 Collection继承结构&#xff08;基于Java21&#xff09;2.2 Collection接口的常用方法2.3 Collection的遍历&#xff08;集合的通用遍历方式&#xff09;2.4 所有的有序集合都实现了SequencedCollection接口2.5 泛型2.5.1 如何判断是否可以…

防止狗上沙发,写一个浏览器实时识别目标检测功能

家里有一条狗&#x1f436;&#xff0c;很喜欢乘人不备睡沙发&#x1f6cb;️&#xff0c;恰好最近刚搬家 狗迎来了掉毛期 不想让沙发上很多毛。所以希望能识别到狗&#xff0c;然后播放“gun 下去”的音频&#x1f4e3;。 需求分析 需要一个摄像头&#x1f4f7; 利用 chrome…

Mapmost Alpha:开启三维城市场景创作新纪元

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…

vue3中使用antv-S2表格(基础功能版)

先看展示效果&#xff1a; 可以调整行宽、列宽、自定义字段图标、表头图标、添加排序、显示总计、小计等 首先确保搭建一个vue3项目环境&#xff0c;从0开始的小伙伴着重看第一点&#xff1a; 一、搭建vue3项目环境 首先创建一个vue3vitets项目&#xff0c;可以查看下面相关…

头歌-机器学习实验 第8次实验 决策树

第1关&#xff1a;什么是决策树 任务描述 本关任务&#xff1a;根据本节课所学知识完成本关所设置的选择题。 相关知识 为了完成本关任务&#xff0c;你需要掌握决策树的相关基础知识。 引例 在炎热的夏天&#xff0c;没有什么比冰镇后的西瓜更能令人感到心旷神怡的了。现…

Spark-Scala语言实战(16)

在之前的文章中&#xff0c;我们学习了三道任务&#xff0c;运用之前学到的方法。想了解的朋友可以查看这篇文章。同时&#xff0c;希望我的文章能帮助到你&#xff0c;如果觉得我的文章写的不错&#xff0c;请留下你宝贵的点赞&#xff0c;谢谢。 Spark-Scala语言实战&#x…

使用doop识别近commons text漏洞的污点信息流

一、doop静态分析框架简介 1. doop静态分析框架简介 doop静态分析框架由希腊雅典大学plast-lab Yannis Smaragdakis团队设计开发&#xff0c;目前看是一款开源领域的比较先进的程序静态分析框架&#xff0c;一些程序静态分析论文的理论也有通过doop的规则实现后实验。 doop整…

c 解数独(通用方法,适用于9×9 数独)

折腾了一周时间&#xff0c;终于搞定99数独通用方法 思路&#xff1a;1.生成每行空位的值&#xff0c;也就是1-9中除去非0的数。 2.用行&#xff0c;列&#xff0c;宫判断每行中每个空位的最小取值范围后再重新生成每行。 3.随机提取生成的9行&#xff0c;判断每列之和是否等…

【数据结构与算法】:二叉树经典OJ

目录 1. 二叉树的前序遍历 (中&#xff0c;后序类似)2. 二叉树的最大深度3. 平衡二叉树4. 二叉树遍历 1. 二叉树的前序遍历 (中&#xff0c;后序类似) 这道题的意思是对二叉树进行前序遍历&#xff0c;把每个结点的值都存入一个数组中&#xff0c;并且返回这个数组。 思路&…

解决 IDEA每次打开新的项目都要重新设置maven问题

目录 一、当前项目设置maven 如下图&#xff1a; 二、设置打开的新项目的maven 如下图&#xff1a;​ 一、当前项目设置maven 对于当前项目我们都知道设置maven的配置要在 File -- Settings -- Build -- Maven 中设置 如下图&#xff1a; 二、设置打开的新项目的maven F…

150个 HTML5 网站模版 量大慢选

HTML5 网站模版 No.1 HTML5 网站模版 No.1

linux下安装nacos2.2.0

1、获取下载地址并下载 1.1、打开nacos官网 1.2、找到对应版本&#xff0c;点进去 ## 1.3、复制地址 1.4下载 # 进入要安装的目录&#xff0c;cd /usr/local/src # 执行wget https://github.com/alibaba/nacos/releases/download/2.2.0/nacos-server-2.2.0.tar.gz2、 安装…

RTSP/Onvif安防视频EasyNVR平台 vs.多协议接入视频汇聚EasyCVR平台:设备分组的区别

EasyNVR安防视频云平台是旭帆科技TSINGSEE青犀旗下支持RTSP/Onvif协议接入的安防监控流媒体视频云平台。平台具备视频实时监控直播、云端录像、云存储、录像检索与回看、告警等视频能力&#xff0c;能对接入的视频流进行处理与多端分发&#xff0c;包括RTSP、RTMP、HTTP-FLV、W…

架构设计参考项目系列主题:新零售SaaS架构:客户管理系统架构设计

什么是客户管理系统? 客户管理系统,也称为CRM(Customer Relationship Management),主要目标是建立、发展和维护好客户关系。 CRM系统围绕客户全生命周期的管理,吸引和留存客户,实现缩短销售周期、降低销售成本、增加销售收入的目的,从而提高企业的盈利能力和竞争力。 …

【ARM 裸机】汇编 led 驱动之原理分析

1、我们为什么要学习汇编&#xff1f;&#xff1f;&#xff1f; 之前我们或许接触过 STM32 以及其他的 32 位的 MCU ,都是基于 C 语言环境进行编程的&#xff0c;都没怎么注意汇编&#xff0c;是因为 ST 公司早已将启动文件写好了&#xff0c;新建一个 STM32 工程的时候&#…