n个任务要M个机器完成
- //题目大意:公司现有n个任务要完成，每份任务有它的花费时间xi,等级yi,而公司有m机器,每台机器也有它的限制时间为xi,等级为yi,每台机器只能处理时间和等级都不大于自己的任务
- //每台机器每天只能完成一个任务,每个任务也只能被一个机器完成,完成任务task(xi,yi)可以获得金钱(500*xi+2*yi),已知现在有n个任务和m台机器，公司首先想要保证每天完成最多的任务，如果有许多方案可以满足，那么最多可以赚多少钱？
- //思路:这里我们借助一个数组Level[i] 记录等级为i的机器的数量
- //①题目说,每个任务的价值是(500*xi+2*yi), xi(0
- //②假设有2个任务t1,t2:当遍历到任务t1时，把时间和等级都>=t1的机器加入到level中来,接着在level数组中找等级最接近的机器处理掉t1，成功处理金钱ans增加
- //④当遍历任务t2时，把时间和等级都>=t2的机器加入到level中来,我这里叫他们做"新机器“，上一层留下的旧机器还放在level数组中,如果旧机器无法处理t2（时间绝对是够的,但是可能等级不够）,那么新机器就可以处理t2,如果没有新机器就业无法处理
- //为何选择这个方案??按上面的过程,假如mach1处理了t1, 到了t2的时候,如果mach1也可以处理t2,但是t1的价值比t2大，所以可以保证金钱最多,如果mach1不能处理t2，那么就保证了处理的任务最多。所以这个方案是最优的。
- //不要使用qsort，否则报错..
【n个任务要M个机器完成】package test1;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeMap;
public class a {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
//while(scanner.hasNext()){
//String s1=scanner.nextLine();
//int a=scanner.nextInt(); //机器
// int b=scanner.nextInt(); //任务
// int[][] mec=new int[a][2];
// int[][] task=new int[b][2];
// int i=0,j=0;
// while(a>0){//机器
//
// int s1=scanner.nextInt();
// int s2=scanner.nextInt();
// mec[i][0]=s1;
// mec[i][1]=s2;
// i++;
// a--;
// }
//
// while(b>0){//任务
// int s3=scanner.nextInt();
// int s4=scanner.nextInt();
// task[j][0]=s3;
// task[j][1]=s4;
// j++;
// b--;
// }
int[][] task={{100,3},{100,2}};
int[][] mec={{100,3},{100,2},{100,1}};
int a=mec.length;
int b=task.length;
qSort(mec,0,a-1); //机器按降序进行排列，当时间相同时，按等级降序
qSort(task,0,b-1); //任务按降序排序
//接下来要对这两组数进行选择，先把任务时间大于机器时间并且任务等级大于机器等级的数组选择出来
int count=0;
int sum=0;
boolean[] flag=new boolean[a];
for(int i=0; i flag[i]=true; //设置标签，为了确保该机器没有被占用
}
for(int x=0; x
for(int y=0; y if(task[x][0]<=mec[y][0]&&task[x][1]<=mec[y][1]&&flag[y]==true){
list.add(y);
}
}//上面是能够完成一个任务的机器数量
if(list.size()<=0) break;
else{
count++;
int min=Integer.MIN_VALUE;
int m=0;
for(int i=0; i
if(mec[m][1]
flag[m]=false;
}
//System.out.println(task[x][1]);
sum+=200*task[x][0]+task[x][1]*3;
}
System.out.println(count+" "+sum);
}
// }
private static void qSort(int[][] mec, int low, int high) {
if(low>=high) return;
if(low int p=partition(mec, low, high);
qSort(mec, low, p-1);
qSort(mec, p+1, high);
}
}
private static int partition(int[][] a, int low, int high) {
int[] q=new int[2];
q[0]=a[low][0];
q[1]=a[low][1];
while(low while(low a[low][0]=a[high][0];
a[low][1]=a[high][1];
while(low=0) ++low;
a[high][0]=a[low][0];
a[high][1]=a[low][1];
}
a[low][0]=q[0];
a[low][1]=q[1];
return low;
}
private static int compare(int[] q, int[] a) {
if(q[0]>a[0]) return -1;
if(q[0] if(q[1]>a[1]) return -1;
if(q[1]
return 0;
}
}
推荐阅读
- 我要做大厨
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 一个小故事，我的思考。
- 一个人的碎碎念
- 这辈子我们都不要再联系了
- 猎杀IP
- 七年之痒之后
- 眼光要放高远
- 我从来不做坏事