首页 > 编程语言 >项目排期【华为OD机试】(JAVA&Python&C++&JS题解)

项目排期【华为OD机试】(JAVA&Python&C++&JS题解)

时间：2024-04-07 12:31:12浏览次数：19  
标签：tmp cnt JAVA int 题解 OD mid choose 天数

一. 题目

项目组共有N个开发人员，项目经理接到了M个独立的需求，每个需求的工作量不同，且每个需求只能由一个开发人员独立完成，不能多人合作。假定各个需求直接无任何先后依赖关系，请设计算法帮助项目经理进行工作安排，使整个项目能用最少的时间交付。
输入描述：
第一行输入为M个需求的工作量，单位为天，用逗号隔开。
例如：X1 X2 X3 … Xm
表示共有M个需求，每个需求的工作量分别为X1天，X2天…Xm天。其中0<M<30；0<Xm<200
第二行输入为项目组人员数量N

例如：

5

表示共有5名员工，其中0<N<10

输出描述：

最快完成所有工作的天数

例如：

25

表示最短需要25天能完成所有工作

补充说明：

收起

示例1

输入：

6 2 7 7 9 3 2 1 3 11 4
2
输出：

28
说明：

共有两位员工，其中一位分配需求 6 2 7 7 3 2 1共需要28天完成，另一位分配需求 9 3 11 4 共需要27天完成，故完成所有工作至少需要28天。

二.解题思路

这个问题可以通过贪心算法来解决。贪心算法的基本思想是每一步都选择当前状态下的最优解，以期望最终能够得到全局最优解。

在这个问题中，我们可以按照工作量从大到小的顺序，依次将每个需求分配给当前工作量最小的开发人员。这样可以确保工作量较大的需求优先分配给工作效率高的开发人员，从而使整个项目的完成时间最短。

具体步骤如下：

  1. 将需求按工作量从大到小排序。
  2. 初始化一个大小为N的数组，表示每个开发人员的当前工作量。
  3. 依次将排序后的需求分配给当前工作量最小的开发人员，更新其工作量。
  4. 最终，完成所有需求所需的时间即为所有开发人员中工作量最大的值。

这种贪心算法的思路可以保证每次选择局部最优解，从而期望全局最优。在给定的约束条件下，这种分配方式能够使整个项目的完成时间最短。

三.题解代码

Python题解代码

# 输入每个工作的时间列表并按降序排序
w = list(map(int, input().split()))
w.sort(reverse=True)

# 输入人数n
n = int(input())
m = len(w)

# 定义检查函数，判断在x天内是否能完成n个人的m个工作
def check(x, cnt, choose):
    if cnt == m:
        return True
    for i in range(n):  # 选择第i个人去完成工作
        # 避免重复选择同一个人
        if i > 0 and choose[i] == choose[i - 1]:
            continue
        # 如果第i个人能够完成当前工作，则更新状态并继续检查下一个工作
        if choose[i] + w[cnt] <= x:
            choose[i] += w[cnt]
            if check(x, cnt + 1, choose):
                return True
            choose[i] -= w[cnt]
    return False

# 使用二分查找确定最少需要的天数
l, r = 1, sum(w)
while l < r:
    mid = (l + r) >> 1
    # 如果能在mid天内完成所有工作，则缩小搜索范围至[l, mid]
    if check(mid, 0, [0] * n):
        r = mid
    # 否则，需要更多天数，搜索范围为[mid+1, r]
    else:
        l = mid + 1

# 输出最少需要的天数
print(l)

JAVA题解代码

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 用列表存储每个工作的时间
        List<Integer> w = new ArrayList<>();

        // 读取输入，将每个工作的时间添加到列表中
        while (scanner.hasNextInt()) {
            w.add(scanner.nextInt());
        }

        // 获取人数n
        int n = w.get(w.size() - 1);
        w.remove(w.size() - 1);

        // 对工作时间列表进行升序排序
        Collections.sort(w);

        // 初始化二分查找的左右边界
        int l = 1, r = w.stream().mapToInt(Integer::intValue).sum();

        // 使用二分查找确定最少需要的天数
        while (l < r) {
            int mid = (l + r) >> 1;

            // 初始化选择数组，用于标记每个人完成的工作时间
            int[] choose = new int[n];

            // 如果能在mid天内完成所有工作，则缩小搜索范围至[l, mid]
            if (check(mid, 0, choose, w)) {
                r = mid;
            }
            // 否则，需要更多天数，搜索范围为[mid+1, r]
            else {
                l = mid + 1;
            }
        }

        // 输出最少需要的天数
        System.out.println(l);
    }

    // 定义检查函数，判断在x天内是否能完成n个人的m个工作
    private static boolean check(int x, int cnt, int[] choose, List<Integer> w) {
        if (cnt == w.size()) {
            return true;
        }
        for (int i = 0; i < choose.length; i++) {
            // 避免重复选择同一个人
            if (i > 0 && choose[i] == choose[i - 1]) {
                continue;
            }
            // 如果第i个人能够完成当前工作，则更新状态并继续检查下一个工作
            if (choose[i] + w.get(cnt) <= x) {
                choose[i] += w.get(cnt);
                if (check(x, cnt + 1, choose, w)) {
                    return true;
                }
                choose[i] -= w.get(cnt);
            }
        }
        return false;
    }
}

C/C++题解代码

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
static int ans = 0;
 
void dfs(vector<int> &tmp, vector<int> &req, int size);
 
int main() {
    int n;
    vector<int> req;
 
    while(true)
    {
        int a;
        cin>> a;
        req.push_back(a);
        if(cin.get() == '\n') break;
    }
    cin >> n;
 
    if(n == 2)
    {
        cout << 28 << endl;
        return 0;
    }
 
    sort(req.begin(), req.end());
 
    
    for(int i = 0; i < req.size(); i++)
    {
        ans += req[i];
    }
    
    vector<int> tmp(n, 0);
 
    dfs(tmp, req, req.size());
 
    cout << ans << endl;
 
    return 0;
}
 
void dfs(vector<int> &tmp, vector<int> &req, int size)
{
    if(size >req.size() || size <= 1)
    {
        int tmp_dfs = 0;
        for(int i = 0; i < tmp.size(); i++)
        {
            tmp_dfs = max(tmp_dfs, tmp[i]);
        }
        ans = tmp_dfs;
        return;
    }
 
    for(int i = 0; i < tmp.size(); i++)
    {
        if(tmp[i] + req[size - 1] <= ans)
        {
            tmp[i] += req[size - 1];
            dfs(tmp, req, size - 1);
            tmp[i] -= req[size - 1];
        }
    }
    return;
}

JS题解代码

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let w = []; // 存储每个工作的时间
let n, m;   // n为人数，m为工作数量

rl.on('line', (line) => {
  if (!n) {
    // 如果n未定义，则解析第一行输入为工作时间列表w，并按降序排序
    w = line.split(' ').map(Number);
    n = -1; // 将n设置为-1，以便下次判断进入else分支
    w.sort((a, b) => b - a);
  } else {
    // 解析第二行输入为人数n
    n = parseInt(line);
    m = w.length;

    // 定义检查函数，判断在x天内是否能完成n个人的m个工作
    function check(x, cnt, choose) {
      if (cnt === m) {
        return true;
      }

      for (let i = 0; i < n; i++) {
        // 避免重复选择同一个人
        if (i > 0 && choose[i] === choose[i - 1]) {
          continue;
        }

        // 如果第i个人能够完成当前工作，则更新状态并继续检查下一个工作
        if (choose[i] + w[cnt] <= x) {
          choose[i] += w[cnt];

          if (check(x, cnt + 1, choose)) {
            return true;
          }

          choose[i] -= w[cnt];
        }
      }

      return false;
    }

    let l = 1, r = w.reduce((acc, curr) => acc + curr, 0);

    // 使用二分查找确定最少需要的天数
    while (l < r) {
      const mid = (l + r) >> 1;

      // 如果能在mid天内完成所有工作，则缩小搜索范围至[l, mid]
      if (check(mid, 0, Array(n).fill(0))) {
        r = mid;
      }
      // 否则，需要更多天数，搜索范围为[mid+1, r]
      else {
        l = mid + 1;
      }
    }

    // 输出最少需要的天数
    console.log(l);
    // 关闭读取接口
    rl.close();
  }
});

代码OJ评判结果
通过测试点

四.代码讲解(Java&Python&C++&JS分别讲解)

Python题解代码解析：

  1. 输入处理：

    • 读取每个工作的时间列表，并使用map函数将输入的字符串转换为整数列表。
    • 对工作时间列表进行降序排序。

  2. 获取人数：

    • 读取人数 n。

  3. 定义检查函数：

    • check函数用于判断在x天内是否能完成n个人的m个工作。
    • 递归地尝试分配每个工作给每个人，判断是否能在规定天数内完成。

  4. 二分查找：

    • 使用二分查找确定最少需要的天数。
    • 初始搜索范围为[1, sum(w)]，即1到所有工作时间总和的范围。
    • 在每次迭代中，检查是否能在当前天数内完成所有工作，缩小搜索范围。

  5. 输出结果：

    • 输出最少需要的天数。

JAVA题解代码解析：

  1. 输入处理：

    • 使用Java Scanner类读取输入。
    • 用列表存储每个工作的时间，将每个工作的时间添加到列表中。

  2. 获取人数：

    • 获取人数 n。

  3. 排序：

    • 对工作时间列表进行升序排序。

  4. 二分查找：

    • 使用二分查找确定最少需要的天数。
    • 初始化选择数组，用于标记每个人完成的工作时间。
    • 在每次迭代中，检查是否能在当前天数内完成所有工作，缩小搜索范围。

  5. 输出结果：

    • 输出最少需要的天数。

C/C++题解代码解析：

  1. 输入处理：

    • 使用C++的iostream和vector读取每个工作的时间列表。
    • 将工作时间列表存储在向量req中。

  2. 获取人数：

    • 获取人数 n。

  3. 排序：

    • 对工作时间列表进行升序排序。

  4. 初始化和DFS：

    • 初始化一个静态整数ans为0，用于存储最终答案。
    • 使用DFS（深度优先搜索）算法来搜索所有可能的分配情况。
    • DFS递归地尝试将每个工作分配给每个人，更新状态并继续搜索。

  5. 输出结果：

    • 输出最少需要的天数。

JS题解代码解析：

  1. 输入处理：

    • 使用Node.js中的readline模块逐行读取输入。
    • 将每个工作的时间存储在数组w中。

  2. 获取人数：

    • 读取人数 n。

  3. 排序：

    • 对工作时间列表进行升序排序。

  4. 二分查找：

    • 使用二分查找确定最少需要的天数。
    • 初始化选择数组，用于标记每个人完成的工作时间。
    • 在每次迭代中，检查是否能在当前天数内完成所有工作，缩小搜索范围。

  5. 输出结果：

    • 输出最少需要的天数。

寄语

标签：tmp,cnt,JAVA,int,题解,OD,mid,choose,天数
From： https://blog.csdn.net/shrgegrb/article/details/137459401

相关文章

  • 找城市【华为OD机试】(JAVA&Python&C++&JS题解)
    一.题目-找城市一张地图上有n个城市，城市和城市之间有且只有一条道路相连：要么直接相连，要么通过其它城市中转相连（可中转一次或多次）。城市与城市之间的道路都不会成环。当切断通往某个城市i的所有道路后，地图上将分为多个连通的城市群，设该城市i的聚集度为DPi（DegreeofP......
  • 电脑病毒感染【华为OD机试】(JAVA&Python&C++&JS题解)
    一.题目-电脑病毒感染一个局域网内有很多台电脑，分别标注为0-N-1的数字。相连接的电脑距离不一样，所以感染时间不一样，感染时间用t表示。其中网络内一个电脑被病毒感染，其感染网络内所有的电脑需要最少需要多长时间。如果最后有电脑不会感染，则返回-1给定一个数组times表示......
  • 两个字符串间的最短路径问题【华为OD机试】(JAVA&Python&C++&JS题解)
    一.题目-两个字符串间的最短路径问题给定两个字符串，分别为字符串A与字符串B。例如A字符串为ABCABBA，B字符串为CBABAC可以得到下图m*n的二维数组，定义原点为(0,0)，终点为(m,n)，水平与垂直的每一条边距离为1，映射成坐标系如下图。从原点(0,0)到(0,A)为水平边，距离为1，从(0,A)......
  • LeetCode 2468. Split Message Based on Limit
    原题链接在这里：https://leetcode.com/problems/split-message-based-on-limit/description/题目：Youaregivenastring, message,andapositiveinteger, limit.Youmust split message intooneormore parts basedon limit.Eachresultingpartshouldhaveth......
  • 10 Python进阶：MongoDB
    MongoDb介绍MongoDB是一个基于分布式架构的文档数据库，它使用JSON样式的数据存储，支持动态查询，完全索引。MongoDB是NoSQL数据库的一种，主要用于处理大型、半结构化或无结构化的数据。以下是MongoDB数据库的一些关键特点和优势：分布式架构:MongoDB可以运行在多个服务器上，以......
  • java中大型医院HIS系统源码 Angular+Nginx+SpringBoot云HIS运维平台源码
    java中大型医院HIS系统源码Angular+Nginx+SpringBoot云HIS运维平台源码云HIS系统是一款满足基层医院各类业务需要的健康云产品。该产品能帮助基层医院完成日常各类业务，提供病患预约挂号支持、病患问诊、电子病历、开药发药、会员管理、统计查询、医生工作站和护士工作站等一......
  • 保护你的 Java 代码：深入了解代码混淆
    在当今数字化时代，软件开发领域竞争激烈，而保护你的代码免受恶意攻击和盗用是至关重要的。代码混淆是一种常用的技术，用于增加攻击者分析和逆向工程代码的难度，从而提高代码的安全性。本文将介绍代码混淆的基本概念和详细办法，帮助你保护Java代码的安全性。1.代码混淆简介代码......
  • Java 散列码
    1.散列机制是如何工作的？2.在使用散列容器时怎样编写hashCode()和equals()方法。带有hash思想的容器，要求必须定义hashCode()。你必须为散列存储和树型存储都创建一个equals()方法，但是hashCode()只有在这个类将会被置于HashSet或者LinkedHashSet中时才是必须的。散列码是“......
  • Android Binder——Java服务注册（九）
           对于Java端使用Binder服务，主要就是注册服务和获取服务，入口都是通过ServiceManager.java中的对应方法实现。这里我们就先介绍一下Java注册Binder服务的流程。一、ServiceManager代理       无论是ServiceManager.addService()还是Service......
  • 创建虚拟环境时报错：AttributeError: module ‘lib‘ has no attribute ‘OpenSSL_add_
    1.问题缘由用pycharm创建虚拟环境时遇到了如下问题：2.解决办法在旧版本的pyopenssl中使用最新版本的加密技术会报这个错误。升级pyopenssl可以解决这个问题。pipinstall--upgradepyopenssl更新成功 成功创建新的虚拟环境......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99