携程笔试 任务调度-贪心算法ac
基本思路：
1.如果节点个数和任务个数有一个为0，则输出0
2.如果节点个数大于等于任务个数，则输出任务里面耗时最大的那个
3.如果节点个数小于任务个数
（1）先把所有任务的耗时相加起来，相加之和除以节点，如果可以整除则直接整除，否则向上取整，这一步得到一个均值为jVal
（2）从jVal开始判断，如果jVal满足被调度的最小时间，则输出，否则jVal加1 继续判断
ps：判断方法：贪心选择，对任务数组进行遍历，累加遍历的时间，如果当前累计值>=jVal，则令累计值为0或者为最后加的那个耗时，同时不要忘记判断一共有多少个区间满足累加值<=jVal 如果区间数小于m，才可以说这个jVal满足条件。
下面是代码：
package xiechenglvxing;
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Main3 {
static boolean judgeAns(int ans,int[]array,int m){
int cpuNodes=0;
int temp=0;
for(int i=0;i<array.length;i++){
if(temp+array[i]<ans){
if(i==array.length-1)
cpuNodes++;
temp+=array[i];
}else if(temp+array[i]==ans){
cpuNodes++;
temp=0;
}else if(temp+array[i]>ans){
if(i==array.length-1){
temp+=array[i];
}else{
cpuNodes++;
temp=array[i];
}
}
}
if(temp<=ans&&cpuNodes<=m)
return true;
else
return false;
}
static int schedule(int m,int[] array) {
if(m==0||array.length==0)
return 0;
if(m>=array.length){
int ans=Integer.MIN_VALUE;
for(int i=0;i<array.length;i++){
if(array[i]>ans)
ans=array[i];
}
return ans;
}
//节点数小于任务数
int len=array.length;
int jval=0;
for(int i=0;i<len;i++)
jval+=array[i];
//均值向上取整
if(jval%m==0){
jval=jval/m;
}else{
jval=jval/m+1;
}
for(int i=jval;;i++){
if(judgeAns(i,array,m)){
return i;
}
}
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int m = in.nextInt();
int size = in.nextInt();
int[] array = new int[size];
for(int i = 0; i < size; i++) {
array[i] = in.nextInt();
}
int res = schedule(m,array);
System.out.println(String.valueOf(res));
}
}
投递58到家等公司10个岗位 >
