首页 > 试题广场 >

安排机器

[编程题]安排机器

热度指数：8475 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小Q的公司最近接到m个任务, 第i个任务需要xi的时间去完成, 难度等级为yi。
小Q拥有n台机器, 每台机器最长工作时间zi, 机器等级wi。
对于一个任务,它只能交由一台机器来完成, 如果安排给它的机器的最长工作时间小于任务需要的时间, 则不能完成,如果完成这个任务将获得200 * xi + 3 * yi收益。

对于一台机器,它一天只能完成一个任务, 如果它的机器等级小于安排给它的任务难度等级, 则不能完成。

小Q想在今天尽可能的去完成任务, 即完成的任务数量最大。如果有多种安排方案,小Q还想找到收益最大的那个方案。小Q需要你来帮助他计算一下。

输入描述:

输入包括N + M + 1行,
输入的第一行为两个正整数n和m(1 <= n, m <= 100000), 表示机器的数量和任务的数量。
接下来n行,每行两个整数zi和wi(0 < zi < 1000, 0 <= wi <= 100), 表示每台机器的最大工作时间和机器等级。
接下来的m行,每行两个整数xi和yi(0 < xi < 1000, 0 <= yi<= 100), 表示每个任务需要的完成时间和任务的难度等级。

输出描述:

输出两个整数, 分别表示最大能完成的任务数量和获取的收益。

示例1

输入

输出

1 20006

算法知识视频讲解

Java

lalalahs

这道题明显出得有问题，时长产生的收益不可能永远高于难度等级的，因为收益=200*时长+等级*3，时长最小步长是1*200，而等级跨度最大有100*3，以时长为单目标作优化肯定是错的，可是测试用例却根本不考虑这种情况，简单的单目标贪心的代码就能AC。

例子：

1 2
999 100
2 1
1 100
答案： 1（个任务） 500（个收益）。贪心的错误答案收益是403

但是，如果不用单目标贪心，复杂度就要上去了，这是我写的用递归方法遍历树的方法搜索任务和机器的匹配空间代码，可以跑对我自己编的各式各样的试错例子，但是贴上去40%就超时了，扎心了。

跪求个大佬指点一下，有没有复杂度又低又能照顾到正确收益的方法o(╥﹏╥)o

import java.util.*;
public class Main{


public static void main(String[] args)
{

Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int m = sr.nextInt();
node [] e = new node[n];
node [] f = new node[m];
for(int i=0;i<n;i++)
{
e[i] = new node(sr.nextInt(),sr.nextInt());
}
for(int i=0;i<m;i++)
{
f[i] = new node(sr.nextInt(),sr.nextInt());
}
Comparator<node> cp = new Comparator<node>() {
@Override
public int compare(node a, node b) {
return b.benefit-a.benefit;
}
};// 降序排
Arrays.sort(e, cp);
Arrays.sort(f, cp);

long[] res = go(e, f, new long[2], 0); //res[0]完成任务数， res[1]总收益

System.out.println(res[0]+" "+res[1]);
sr.close();
}
static long[] go(node[]e, node[]f, long[] oldres, int idx)
{

long bestRes[] = {oldres[0], oldres[1]};
boolean found = false;
for(int i=0;i<e.length && e[i].benefit>=f[idx].benefit;i++)
{
if(e[i].occupied||e[i].t<f[idx].t||e[i].w<f[idx].w)continue;
found = true;
long res[] = {oldres[0], oldres[1]};
e[i].occupied = true;
++res[0];
res[1] += f[idx].benefit;
if(idx+1<f.length)
res = go(e, f, res, idx+1);
e[i].occupied = false;
if(res[0]>bestRes[0] || (res[0] == bestRes[0] && res[1]>bestRes[1]))
{
bestRes[0] = res[0];
bestRes[1] = res[1];
}
}
if(!found && idx+1<f.length)bestRes = go(e, f, bestRes, idx+1);
return bestRes;
}

}
class node{
final int t;
final int w;
final int benefit;
boolean occupied; //机器被占了吗
node(int t, int w)
{
this.t = t;
this.w = w;
this.benefit = t*200+w*3;
this.occupied = false;
}
}

编辑于 2019-08-27 10:33:33 回复(7)

Java

小K姐姐

60%，卡在的这个用例有10个任务，我算的是都可以完成，而且把对应情况打印出来看确实可以啊，不太明白哪里出了问题...大家帮忙看看

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in); while(sc.hasNext()){ int n=sc.nextInt(); //n台机器  int m=sc.nextInt(); //m个任务  Node[]machines =new Node[n];
        Node []tasks=new Node[m]; for (int i = 0; i < n; i++) {
            machines[i]=new Node(sc.nextInt(),sc.nextInt());
        } for (int i = 0; i < m; i++) {
            tasks[i]=new Node(sc.nextInt(),sc.nextInt());
        }
        PriorityQueue<Node>maxHeap=new PriorityQueue<>(new Comparator<Node>() { @Override//缓冲池1，根据时间解锁后的数据先进入这里，按照等级由高到低排序，等级大于解锁池的进入解锁池  public int compare(Node o1, Node o2) { return o2.label-o1.label;
            }
        });
        PriorityQueue<Node>minHeap=new PriorityQueue<>(new Comparator<Node>() {//启动池  @Override//解锁池按等级由低到高排序，即先用掉等级低的  public int compare(Node o1, Node o2) { return o1.label-o2.label;
            }
        });
        Arrays.sort(tasks, new MyComparator()) ;//任务由难到简单排序  Arrays.sort(machines,new MyComparator());//机器由高到低排序   int num=0; long profit=0; int j=0; for (int i = 0; i <m; i++) { while(j<n&&tasks[i].time<=machines[j].time){//时间满足条件的全部进入缓冲池1  maxHeap.add(machines[j]);
                j++;
            } while(!maxHeap.isEmpty()&&maxHeap.peek().label>=tasks[i].label){ //等级满足条件，进入解锁池  minHeap.add(maxHeap.poll());
            } if(!minHeap.isEmpty()){ //有满足条件的数据  Node cur=minHeap.poll();
                num++;
                System.out.println("机器"+cur.time+" "+cur.label+"完成的任务是："+tasks[i].time+" "+tasks[i].label);
                profit+=200*tasks[i].time+3* tasks[i].label;//默认此时获得的利润则为最大  }
        }
        System.out.println(num+" "+profit);
    }
} public static class MyComparator implements Comparator<Node>{ @Override  public int compare(Node o1, Node o2) { if(o1.time!=o2.time){ return o2.time-o1.time;//按需要时长从大到小排序  } return o2.label-o1.label;//按需要等级从大到小排序   }
} public static class Node{ int time; int label; public Node(int time, int label) { this.time = time; this.label = label;
    }
}