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];
        }
        else
            a[s] += ti[i];
    }
    if (s > k)
    { // 人数>k
        return 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;
        else
            cout << 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;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Qt5中使用QPrinter和QprintDialog类

学习Qt过程中&#xff0c;做一个简单的编辑器&#xff0c;其中需要使用到打印文本功能&#xff0c;在使用Qt printer时遇到了几个麻烦。 一、在使用到QPrinter和QprintDialog类时的附加处理 ①若是在qt creator中&#xff0c;需要在 &#xff08;.pro&#xff09;工程文件中加…

inner join和left semi join的联系和区别

参考&#xff1a;添加链接描述 添加链接描述 1 简介 LEFT SEMI JOIN &#xff08;左半连接&#xff09;是 IN/EXISTS 子查询的一种更高效的实现。 示例 可以改写为 2 特点 1、left semi join 的限制是&#xff0c; JOIN 子句中右边的表只能在 ON 子句中设置过滤条件&…

Python学习从0开始——项目一day01爬虫

Python学习从0开始——项目一day01爬虫 一、导入代码二、使用的核心库三、功能测试3.1初始代码3.2新建文件3.3代码调试 四、页面元素解析4.1网页4.2修改代码4.3子页面4.4修改代码 一、导入代码 在Inscode新建一个python类型的项目&#xff0c;然后打开终端&#xff0c;粘贴以下…

[通俗易懂]《动手学强化学习》学习笔记2-第2、3、4章

文章目录 前言小总结&#xff08;前文回顾&#xff09;第二章 多臂老虎机2.2.2形式化描述 第三章 马尔可夫决策过程3.6 占用度量 代码3.6 占用度量 定理2 第四章 动态规划算法4.3.3 策略迭代算法 代码 总结 前言 参考&#xff1a; 《动手学强化学习》作者&#xff1a;张伟楠&a…

使用 Docker 部署 Open-Resume 在线简历平台

1&#xff09;Open-Resume 介绍 GitHub&#xff1a; https://github.com/xitanggg/open-resume Open-Resume 是一款功能强大的开源 简历生成器 和 简历解析器 。可以帮助我们快速的生成个人简历&#xff0c;并定制化不同的主题和布局风格。该项目的目标是为每个人提供免费的现…

Harmony鸿蒙南向驱动开发-UART

UART指异步收发传输器&#xff08;Universal Asynchronous Receiver/Transmitter&#xff09;&#xff0c;是通用串行数据总线&#xff0c;用于异步通信。该总线双向通信&#xff0c;可以实现全双工传输。 两个UART设备的连接示意图如下&#xff0c;UART与其他模块一般用2线&a…

算法打卡day42|动态规划篇10| Leetcode 121. 买卖股票的最佳时机、122.买卖股票的最佳时机II

算法题 Leetcode 121. 买卖股票的最佳时机 题目链接:121. 买卖股票的最佳时机 大佬视频讲解&#xff1a;121. 买卖股票的最佳时机视频讲解 个人思路 这道题之前贪心算法做过&#xff0c;当然动规也能解决这道题 解法 贪心法 取最左最小值&#xff0c;取最右最大值&#x…

CSS设置首字母大小写和首行样式

一、首字母大小写 1.代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><title>Document</title&…

顺序表(增删减改)+通讯录项目(数据结构)

什么是顺序表 顺序表和数组的区别 顺序表本质就是数组 结构体初阶进阶 系统化的学习-CSDN博客 简单解释一下&#xff0c;就像大家去吃饭&#xff0c;然后左边是苍蝇馆子&#xff0c;右边是修饰过的苍蝇馆子&#xff0c;但是那个好看的苍蝇馆子一看&#xff0c;这不行啊&a…

校园论坛系统

文章目录 校园论坛系统一、项目演示二、项目介绍三、10000字论文参考四、系统部分功能截图五、部分代码展示六、底部获取项目和10000字论文参考&#xff08;9.9&#xffe5;&#xff09; 校园论坛系统 一、项目演示 校园论坛系统 二、项目介绍 基于springbootvue的前后端分离…

【JSON2WEB】 13 基于REST2SQL 和 Amis 的 SQL 查询分析器

【JSON2WEB】01 WEB管理信息系统架构设计 【JSON2WEB】02 JSON2WEB初步UI设计 【JSON2WEB】03 go的模板包html/template的使用 【JSON2WEB】04 amis低代码前端框架介绍 【JSON2WEB】05 前端开发三件套 HTML CSS JavaScript 速成 【JSON2WEB】06 JSON2WEB前端框架搭建 【J…

antd+Vue 3实现table行内upload文件图片上传【超详细图解】

目录 一、背景 二、效果图 三、代码 一、背景 一名被组长逼着干前端的苦逼后端&#xff0c;在一个晴天霹雳的日子&#xff0c;被要求前端订单产品实现上传产品图片并立刻回显图片。 二、效果图 三、代码 <template><a-table :dataSource"dataSource" :c…

前端三剑客 —— JavaScript (第七节)

内容回顾 DOM编程 document对象 有属性 有方法 节点类型 元素节点 属性节点 文本节点 操作DOM属性 DOM对象.属性名称 DOM对象[属性名称] 调用DOM对象的API 操作DOM样式 获取有单位的样式值 标签对象.style.样式名称&#xff0c;这种方式只能操作行内样式。 使用getComputedSty…

[Linux][进程概念][进程优先级]详细解读

目录&#xff09; 0.冯诺依曼体系结构1.操作系统(Operator System)1.概念2.设计OS的目的3.定位4.系统调用和库函数概念5.总结 2.进程1.基本概念2.描述进程 -- PCB3.task_struct内容分类4.组织进程5.查看进程6.通过系统调用获取进程标识符7.通过系统调用创建进程 -- fork初识8.进…

44---MSATA电路设计

视频链接 mSATA & mini-pcie电路设计01_哔哩哔哩_bilibili mSATA电路设计 1、mSATA简介 1.1、mSATA基本介绍 mSATA接口是标准SATA的迷你版本&#xff0c;通过mini PCI-E界面传输信号&#xff0c;传输速度支持1.5Gbps、3Gbps、6Gbps三种模式。mSATA接口的诞生&#xff…

数据可视化的3D问题

三维对象非常流行&#xff0c;但在大多数情况下会对解释图形的准确性和速度产生负面影响。 以下是对涉及 3d 的主要图形类型的回顾&#xff0c;并讨论了它们是否被认为是不好的做法。 1、3D 条形图&#xff1a;不要 这是一个 3d 条形图。 你可能很熟悉这种图形&#xff0c;因为…

自学嵌入式,已经会用stm32做各种小东西了,下一步是什么,研究stm32的内部吗?

是的&#xff0c;深入研究STM32的内部是一个很好的下一步。我这里有一套嵌入式入门教程&#xff0c;不仅包含了详细的视频讲解&#xff0c;项目实战。如果你渴望学习嵌入式&#xff0c;不妨点个关注&#xff0c;给个评论222&#xff0c;私信22&#xff0c;我在后台发给你。 了…

【Vue + keep-alive】路由缓存

一. 需求 列表页&#xff0c;n 条数据项可打开 n 个标签页&#xff0c;同时1条数据项的查看和编辑共用一个标签页。如下所示&#xff1a; 参考 // 主页面 // 解决因 路由缓存&#xff0c;导致 编辑后跳转到该页面 不能实时更新数据 onActivated(() > {getList() })二. 实现…

Java面试题戏剧

目录 第一幕 、第一场&#xff09;某大厦楼下大门前第二场&#xff09;电梯中第三场&#xff09;走廊中 第二幕、第一场&#xff09;公司前台第二场&#xff09;公司卫生间 第三幕、第一场&#xff09;一场异常面试 第四幕 、第一场&#xff09;大厦楼下门口第二场&#xff09;…

实验5 VLAN基础配置

实验5 VLAN基础配置 一、 原理描述二、 实验目的三、 实验内容四、 实验配置五、 实验步骤1.配置IP地址2.检测链路连通性3.创建 VLAN4.配置Access接口5.检验结果6.配置Trunk端口7.检验连通性 一、 原理描述 现代局域网通常配置为等级结构&#xff0c;一个工作组中的主机通过交…