#P3263. 项目排期(200分)
-
1000ms
Tried: 132
Accepted: 26
Difficulty: 1
所属公司 :
华为od
项目排期(200分)
思路:二分答案
首先,我们分析答案是否满足单调性:如果天数越大,就越容易满足条件,如果天数越小,就越不容易满足条件,因此是具备单调性的,可以使用二分答案求解。
我们二分去枚举最终的天数x,判断这N个人是否能在x天内完成所有的任务,其实就是看能否把这些任务分成至多N组,而且每一组的份数都不超过x。
判断的方式我们采用DFS+剪枝的做法处理,其实就是把它抽象为m个物品能否放到N个盒子中,每个盒子的容纳体积上限为x。
JavaScript
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();
}
});
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, Collections.reverseOrder());
// 初始化二分查找的左右边界
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;
}
}
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)
C++
#include<bits/stdc++.h>
using namespace std;
// 定义检查函数,判断在x天内是否能完成n个人的m个工作
bool check(int x, int cnt, vector<int>& choose, vector<int>& w) {
if (cnt == w.size()) {
return true;
}
for (int i = 0; i < choose.size(); 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, w)) {
return true;
}
choose[i] -= w[cnt];
}
}
return false;
}
int main() {
vector<int> w;
int num;
// 读取输入,将每个工作的时间添加到向量中
while (cin >> num) {
w.push_back(num);
}
// 获取人数n
int n = w.back();
w.pop_back();
// 对工作时间向量进行降序排序
sort(w.begin(), w.end(),greater<int>{});
// 初始化二分查找的左右边界
int l = 1, r = accumulate(w.begin(), w.end(), 0);
// 使用二分查找确定最少需要的天数
while (l < r) {
int mid = (l + r) >> 1;
// 初始化选择数组,用于标记每个人完成的工作时间
vector<int> choose(n, 0);
// 如果能在mid天内完成所有工作,则缩小搜索范围至[l, mid]
if (check(mid, 0, choose, w)) {
r = mid;
}
// 否则,需要更多天数,搜索范围为[mid+1, r]
else {
l = mid + 1;
}
}
// 输出最少需要的天数
cout << l << endl;
return 0;
}
题目描述
项目组共有N个开发人员,项目经理接到了M个独立的需求,每个需求的工作量不同,且每个需求只能由一个开发人员独立完成,不能多人合作。
假定各个需求直接无任何先后依赖关系,请设计算法帮助项目经理进行工作安排,使整个项目能用最少的时间交付。
输入描述
第一行输入为M个需求的工作量,单位为天,用逗号隔开。
例如:
X1 X2 X3 ... Xm 表示共有M个需求,每个需求的工作量分别为X1天,X2天,…,Xm天。其中:
0 < M < 30 0 < Xm < 200 第二行输入为项目组人员数量N,
例如:
5 表示共有5名员工,其中0 < N < 10
输出描述
- 最快完成所有工作的天数,
样例1
输入
6 2 7 7 9 3 2 1 3 11 4
2
输出
28