首页 > 试题广场 >

安排机器

[编程题]安排机器
  • 热度指数:8452 时间限制: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 2
100 3
100 2
100 1

输出

1 20006
import sys

class node():
    def __init__(self,time,level):
        self.time = time
        self.level = level
#读取第一行获取机器数量和任务数量
line = list(map(int,list(sys.stdin.readline().strip().split(' '))))
machineNum = line[0]
jobNum = line[1]
machines = []
jobs = []
#读取每台机器的最大工作时间和机器等级
for i in range(machineNum):
    machineInfo = list(map(int,list(sys.stdin.readline().strip().split(' '))))
    time = machineInfo[0]
    level = machineInfo[1]
    machine = node(time,level)
    machines.append(machine)
#读取每个任务需要的完成时间和任务的难度系数
for j in range(jobNum):
    jobInfo = list(map(int,list(sys.stdin.readline().strip().split(' '))))
    time = jobInfo[0]
    level = jobInfo[1]
    job = node(time,level)
    jobs.append(job)
#根据时间排序
machines.sort(key = lambda x:(x.time,x.level),reverse = True)
jobs.sort(key = lambda x:(x.time,x.level),reverse = True)
#收益
profit = 0
count = 0
level = [0]*105
#对job根据时间排序,先完成时间大的收益更多;对符合条件的机器选择最接近的level
j = 0
for i in range(jobNum):#循环选取时间最大的job
    #在时间条件(机器时间>任务时间)满足的情况下
    while j< machineNum and machines[j].time>=jobs[i].time:
        level[machines[j].level] += 1
        j += 1
    for k in range(jobs[i].level,101):
        if level[k]:
            count += 1
            level[k] -= 1
            profit += 200 * jobs[i].time + 3 * jobs[i].level
            break
print(count,end=' ')
print(profit)




发表于 2018-08-03 17:56:29 回复(5)
这是牛客名企校招给的答案,我把关键变量都重新命名了一遍,更加方便理解(这是第一次觉得变量命名如此重要)
任务 时间 难度
机器 最长工作时间 及其等级
1 x1 y1
1 z1 w1
2 x2 y1
2 z2 w2
... ... ...
.... ... ...
m xm ym
n zn wn

解决方案:

1、对机器和任务都分别进行排序:时间从大到小,时间相同的按照等级由大到小(cmp完成)

2、对每一个任务进行循环:(第一个 for 循环)

第一个 while 找到 时间上能够处理当前任务的机器(先忽略等级要求),然后将 cnt 中对应等级位置加一操作

第二个 for 循环,看对应等级上,有没有机器可以处理相应的任务,while循环已经保证了时间上的可操作性

也写在CSDN上了(上面的排版可能要好一些):
//安排机器
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn  = 1e5 + 10;
struct node{  int time,grade;
}machine[maxn],task[maxn]; 

int cnt[105];

int cmp(node a,node b){  if(a.time==b.time){  return a.grade>b.grade;  }  return a.time>b.time;
}

int main(){  int numMachine,numTask;  scanf("%d%d",&numMachine,&numTask);  for(int i=0;i<numMachine;i++){  scanf("%d%d",&machine[i].time,&machine[i].grade);  }  for(int i=0;i<numTask;i++){  scanf("%d%d",&task[i].time,&task[i].grade);  }  sort(machine,machine+numMachine,cmp);  sort(task,task+numTask,cmp);
// for(int i=0;i<numMachine;i++){
// printf("%d %d\n",e[i].time,e[i].grade);
// }
// for(int i=0;i<numTask;i++){
// printf("%d %d\n",f[i].time,f[i].grade);
// }    int num = 0;  LL ans = 0;  memset(cnt,0,sizeof(cnt));  int i,j,k;  for(i=0,j=0;i<numTask;i++){ //对于每个任务而言  while(j<numMachine && machine[j].time>=task[i].time){  cnt[machine[j].grade]++;  j++;  }  for(k=task[i].grade;k<=100;k++){  if(cnt[k]){  num++;  cnt[k]--;  ans = ans+200*task[i].time + 3*task[i].grade;  break;  }  }  }  printf("%d %lld\n",num,ans);  return 0;
}

编辑于 2019-03-20 16:55:57 回复(3)
nums = list(map(int,input().split()))
machine = []
duty = []
for i in range(nums[0]):
    # nums[0]个机器
    machine.append(list(map(int,input().split())))
    (2790)# [zi, wi]
for j in range(nums[1]):
    duty.append(list(map(int,input().split())))
    # [xi, yi]
(2791)# 根据时间排序,若时间一致,则根据等级排序
machine = sorted(machine,key = lambda x:(x[0],x[1]),reverse = True)
duty = sorted(duty,key = lambda x:(x[0],x[1]),reverse = True)
# profile = 200*xi+3*yi,说明时间大的收益更多
profile = 0 (2792)#总利润
count = 0 # 计数
j = 0 (2793)# 表示选择第j个机器,选择的机器需要和任务的等级最接近,效率才能最大

# hash_dict = {}
(2794)# #用来存储机器等级的数量,{1:1}表示等级为1的机器有1个
(2795)# for k in range(len(machine)):
#     if machine[1] in  hash_dict:
(2796)#         hash_dict[machine[1]]+= 1
#     else : hash_dict[machine[1]] = 1
(2797)# # 统计后根据等级排序
(2798)# level=sorted(hash_dict.items(),key=lambda x:x[0],reverse=True) 

level = [0 for i in range(200)] 
#用来存储机器等级的数量,level[1]=1表示等级为1的机器有1个
for i in range(len(duty)):
    while j < len(machine) and machine[j][0]>=duty[i][0]:
        level[machine[j][1]]+=1
        j += 1
    for k in range(duty[i][1],200):
        (2799)# 从等级大于等于任务难度的机器中选择
        if level[k]:
            count += 1
            level[k] -= 1
            profile += 200*duty[i][0] + 3*duty[i][1]
            break
print(count,end=' ')
print(profile)
    

发表于 2020-03-18 11:32:48 回复(0)
##感觉没有错呀,测试了一些还能过,方法上用的最简单的栈深度优先搜索,时间效率上不高,容易实现

n, m = input().split()
n, m = int(n), int(m)
zw_list=  []
for i in range(n):
    temp = [int(x) for x in input().split()]
    zw_list.append(temp)
xy_list = []
for i in range(m):
    temp = [int(x) for x in input().split()]
    xy_list.append(temp)

can_finish = [[] for i in range(n)]
for i in range(n):
    for j in range(m):
        if zw_list[i][0] >= xy_list[j][0] and zw_list[i][1] >= xy_list[j][1]:
            can_finish[i].append(j)
#print(can_finish)

stack = []
l_stack = []
start = 0
while len(can_finish[start]) == 0:
    start += 1
for i in range(len(can_finish[start])):
    stack.append(can_finish[start][i])
    l_stack.append(start)


temp_list = []
temp = []
while len(stack):
    s = stack.pop(-1)
    l = l_stack.pop(-1)
    temp.append(s)
    if l == n - 1:
        temp_list.append(temp)
        temp = []
    else:
        for j in range(len(can_finish[l+1])):
            stack.append(can_finish[l+1][j])
            l_stack.append(l+1)
#print(temp_list)
max_num = 0
max_temp_list = []
for temp in temp_list:
    temp = sorted(temp)
    num = 0
    for i in range(len(temp)-1):
        if temp[i] == temp[i + 1]:
            num  += 1
    mn = len(temp) - num
    if mn > max_num:
        max_num = mn
        max_temp_list = [temp]
    elif mn == max_num:
        max_temp_list.append(temp)
#print(max_temp_list)
max_score = 0
for temp in max_temp_list:
    score = 0
    for j in range(len(temp)):
        score += 200 * xy_list[temp[j]][0] + 3 * xy_list[temp[j]][1]
    if score > max_score:
        max_score = score
print(max_num, max_score)


编辑于 2019-04-06 12:19:00 回复(0)
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 1e5 + 10;
struct node {
    int x,y;
}e[maxn],f[maxn];
int cnt[105];
int cmp(node a ,node b){
    if(a.x == b.x)return a.y > b.y;
    return a.x > b.x;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n;i++) scanf("%d%d",&e[i].x,&e[i].y);
    for(int i = 0;i < m;i++) scanf("%d%d",&f[i].x,&f[i].y);
    sort(e,e + n,cmp);
    sort(f,f + m,cmp);
    int num = 0;
    LL ans = 0;
    memset(cnt,0,sizeof(cnt));
    int i,j,k;
    for(i = 0,j = 0;i < m;i++){
        while(j < n && e[j].x >= f[i].x){
            cnt[e[j].y]++;
            j++;
        }
        for(k = f[i].y;k <= 100;k++){
            if(cnt[k]){
                num++;
                cnt[k]--;
                ans = ans + 200 * f[i].x +3 * f[i].y;
                break;
            }
        }
    }
    printf("%d %lld\n",num,ans);
    return 0;
}

发表于 2018-07-15 11:39:37 回复(5)
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 1e5 + 10;
struct node {
    int x, y;
}e[maxn], f[maxn];  //定义两个结构数组
int cnt[105];
int cmp(node a, node b)
{
    if(a.x ==b.x)
        return a.y >b.y;
    return a.x > b.x;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i=0; i<n; i++)
        scanf("%d%d", &e[i].x, &e[i].y);
    for(int i=0; i<m; i++)
        scanf("%d%d", &f[i].x, &f[i].y);
    sort(e, e+n, cmp);
    sort(f, f+m, cmp);
    int num = 0;
    LL ans = 0;
    memset(cnt, 0, sizeof(cnt));
    int i,j,k;
    for(i=0,j=0; i<m; i++)
    {
        while(j<n && e[j].x >= f[i].x){
            cnt[e[j].y]++;
            j++;
        }
        for(k=0; k<=100; k++)
        {
            if(cnt[k] && k>=f[i].y)
            {
                num++;
                cnt[k]--;
                ans += 200*f[i].x + 3*f[i].y;
                break;
            }
        }
    }
    printf("%d %lld\n", num, ans);
    return 0;
}

发表于 2018-08-17 23:05:31 回复(3)

感觉没那么复杂,分为两块,一块求策略集,另一块求排列组合,组合的公式直接套就行,杨辉三角感觉有点过了。本人渣渣python,C和Java之类的不太会

# coding:utf-8
# 小Q的歌单
def match(a, x, b, y, k):
    get = []
    for i in range(x + 1):
        for j in range(y + 1):
            if i * a + j * b == k:
                get.append([i, j])
    return get


def c(i, j):
    a = 1
    b = 1
    tmp_i = i
    tmp_j = j
    while tmp_i >= 1:
        a = a * tmp_j
        b = b * tmp_i
        tmp_i = tmp_i - 1
        tmp_j = tmp_j - 1
    return a / b


k = int(raw_input().strip())
# print(c(2,4))
[a, x, b, y] = [int(i) for i in raw_input().strip().split()]
get = match(a, x, b, y, k)
if len(get) == 0:
    print 0
else:
    result = 0
    for i in get:
        result = result + c(i[0], x) * c(i[1], y)
    print result % 1000000007
发表于 2018-09-14 16:36:52 回复(3)
这道题明显出得有问题,时长产生的收益不可能永远高于难度等级的,因为收益=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)
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

    static class Pair {
        int time;
        int diff;

        public Pair(int time, int diff) {
            this.time = time;
            this.diff = diff;
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int machineNum = sc.nextInt();
            int taskNum = sc.nextInt();
            Pair[] machines = new Pair[machineNum];
            Pair[] tasks = new Pair[taskNum];
            for (int i = 0; i < machineNum; i++) {
                machines[i] = new Pair(sc.nextInt(), sc.nextInt());
            }
            for (int i = 0; i < taskNum; i++) {
                tasks[i] = new Pair(sc.nextInt(), sc.nextInt());
            }
            Comparator<Pair> cmp = new Comparator<Pair>() {

                @Override
                public int compare(Pair p1, Pair p2) {
                    if (p1.time == p2.time) {
                        return p2.diff - p1.diff;
                    } else {
                        return p2.time - p1.time;
                    }
                }

            };
            Arrays.sort(machines, cmp);
            Arrays.sort(tasks, cmp);
            long sum = 0;
            int count = 0;
            int j = 0;
            int[] dp = new int[101];
            for (int i = 0; i < taskNum; i++) {
                while (j < machineNum && machines[j].time >= tasks[i].time) {
                    dp[machines[j].diff]++;
                    j++;
                }
                for (int k = tasks[i].diff; k < 101; k++) {
                    if (dp[k] != 0) {
                        dp[k]--;
                        sum += 200 * tasks[i].time + 3 * tasks[i].diff;
                        count++;
                        break;
                    }
                }
            }
            System.out.println(count + " " + sum);
        }
        sc.close();

    }

}
发表于 2018-05-18 10:42:18 回复(3)
这个测试用例是不是有点杠精?感觉改下收益公式就完美了
1 2
100 3
100 0
99 100
发表于 2018-07-22 23:18:09 回复(0)
num_machine, num_task = map(int, input().split())
machine_list = []
task_list = []

for _i in range(num_machine):
    machine = list(map(int, input().split()))
    machine_list.append(machine)

for _j in range(num_task):
    task = list(map(int, input().split()))
    task_list.append(task)

machine_list.sort(reverse=True)  # 按时间成本从大到小排好
task_list.sort(reverse=True)  # 按时间成本从大到小排好


count = 0  # 完成工作计数
profit = 0  # 利润
level = [0]*101  # 等级列表
j = 0  # 机器计数

for i in range(num_task):
    while j < num_machine and machine_list[j][0] >= task_list[i][0]:
        level[machine_list[j][1]] += 1  # 机器的等级
        j += 1

    for k in range(task_list[i][1], 101):
        if level[k]:  # 如果为1,有机器可以用
            count += 1
            level[k] -= 1
            profit += task_list[i][0]*200 + task_list[i][1]*3
            break

print(count, profit)

发表于 2020-08-23 09:27:17 回复(0)

求大神解答下面的 AC 代码原理

import sys


n_m = list(map(int, sys.stdin.readline().strip().split()))
n, m = n_m[0], n_m[1]
machines, tasks = [], []
for _ in range(n):
    machines.append(list(map(int, sys.stdin.readline().strip().split())))
for _ in range(m):
    tasks.append(list(map(int, sys.stdin.readline().strip().split())))

# 按照 time、level 来排序
machines.sort(key=lambda x: (x[0], x[1]), reverse=True)
tasks.sort(key=lambda x: (x[0], x[1]), reverse=True)

# level 到底用来存储什么?
level = [0 for _ in range(101)]
profit = 0
count = 0
j = 0
for task_time, task_level in tasks:
    while j < n and machines[j][0] >= task_time:
        # 这里为什么要一直加?
        level[machines[j][1]] += 1
        j += 1
    for i in range(task_level, 101):
        if level[i] > 0:
            count += 1
            # 这里为什么要一直减?
            level[i] -= 1
            profit += 200 * task_time + 3 * task_level
            break
print(count, profit)
发表于 2019-04-08 16:17:23 回复(4)
1 2
100 100
100 0
99 100
上面这个用例的答案是1 20100,好多代码都不对
编辑于 2023-11-11 10:47:57 回复(0)
def find_rightst(v, machines):
    left, right = 0, len(machines) - 1
    while left < right:
        mid = (left + right) // 2
        if machines[mid][1] < v:
            left = mid + 1
        elif machines[mid][1] > v:
            right = mid
        else:
            right -= 1
    return left
 
 
def max_value(machines, tasks):
    tasks.sort(key=lambda x: -(200 * x[0] + 3 * x[1]))
    machines.sort(key=lambda x:(x[1], x[0]))
    cnt, values = 0, 0
    visited = [0] * len(machines)
    for left in range(len(tasks)):
        for right in range(find_rightst(tasks[left][1], machines), len(machines)):
            if visited[right]:
                continue
            if tasks[left][1] > machines[right][1]&nbs***bsp;tasks[left][0] > machines[right][0]:
                continue
            else:
                visited[right] = 1
                cnt += 1
                values += tasks[left][0] * 200 + tasks[left][1] * 3
                break
    print(cnt, values)
 
if __name__ == '__main__':
    import sys
    [n, m] = [int(i) for i in sys.stdin.readline().strip().split()]
    machines, tasks = [], []
    for i in range(n):
        machines.append( [int(i) for i in sys.stdin.readline().strip().split()])
    for i in range(m):
        tasks.append( [int(i) for i in sys.stdin.readline().strip().split()])
    max_value(machines, tasks)

发表于 2020-08-14 00:15:48 回复(0)
C++贪心,通不过,请高手指点
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

pair<int, int> fun(vector<pair<int, int>>& machine,
                     vector<pair<int, int>>& task)
{
	sort(machine.begin(), machine.end(),
		 [](pair<int, int>& a, pair<int, int>& b)
		 { return a.first > b.first ||
			(a.first == b.first && a.second > b.second); });
	sort(task.begin(), task.end(),
		 [](pair<int, int>& a, pair<int, int>& b)
		 { return a.first * 200 + a.second * 3 > b.first * 200 + b.second * 3; });
	int n = machine.size(), m = task.size(),
		i = 0, j = 0, cnt = 0, earn = 0;
	vector<int> idx;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (find(idx.begin(), idx.end(), j) == idx.end() &&
				(machine[i].first >= task[j].first &&
				machine[i].second >= task[j].second)) {
				++cnt;
				idx.emplace_back(j);
				break;
			}
		}
	}
	for (const int &i : idx) {
		earn += task[i].first * 200 + task[i].second * 3;
	}
	return make_pair(cnt, earn);
}

int main()
{
	int n, m, z, w, x, y;
	cin >> n >> m;
	vector<pair<int, int>> machine(n), task(m);
	for (int i = 0; i < n; ++i) {
		cin >> z >> w;
		machine[i].first = z;
		machine[i].second = w;
	}
	for (int i = 0; i < m; ++i) {
		cin >> x >> y;
		task[i].first = x;
		task[i].second = y;
	}
	pair<int, int> res = fun(machine, task);
	cout << res.first << " " << res.second << endl;
	return 0;
}


编辑于 2020-05-06 18:18:40 回复(0)
二维偏序下的最大权最大匹配,目前只会KM,O(n^3),时间复杂度太高了,但是问了两个cf红名,三个WF选手,都表示不会做

但是黑红大佬jiangly发现,因为特殊的收益,200x+3y,变得可做了。
首先个数肯定是可以贪心的,对于每个机器选可选的里面x,y最大的能选的。
但是这时候收益不一定最大,但是因为特殊的收益函数,此时只有两种决策,一种是换成一个没选的任务,或者是顶掉一个,但是顶掉一个相当于选的任务的x变成x-2,这样绝对不优,所以只可能是变成x-1的没选的,暴力check下就好了。

编辑于 2020-02-21 14:29:13 回复(0)
求解答,为什么暴力求解只能AC50%??

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
    
};
static int cmp(node t1,node t2)
{
    if(t1.x!=t2.x)
        return t1.x>t2.x;
    else
        return t1.y>t2.y;
 
}


int main(){
int n,m;
cin>>n>>m;
vector<node> jiqi(n);
for(int i=0;i<n;i++)
    cin>>jiqi[i].x>>jiqi[i].y;    //工作时间  等级
vector<node> task(m);
for(int i=0;i<m;i++)
    cin>>task[i].x>>task[i].y;  //任务时间  等级
sort(jiqi.begin(),jiqi.end(),cmp);
sort(task.begin(),task.end(),cmp);   
    
vector<vector<int>> temp(n,vector<int>(m,0));//机器完成任务
int count=0;
int sumvalue=0;
vector<bool> visitjiqi(n,false);
vector<bool> visitask(m,false);  
    
for(int i=0;i<n;i++) //机器
{
 int tempvalue=0;
 int index1=-1;
 int index2=-1;
   if(visitjiqi[i]==false)
   {
    for(int j=0;j<m;j++) //任务
    {
     if(visitask[j]==false)
     {
      if(jiqi[i].x>=task[j].x&&jiqi[i].y>=task[j].y)  
      {
      temp[i][j]=200*task[j].x+3*task[j].y;
      if(tempvalue<temp[i][j])
      {
       tempvalue=temp[i][j];
       index1=i;
       index2=j;
      }
      }
 }
    }  
 if(tempvalue!=0)
 {
     sumvalue+=tempvalue;
     count++;
     visitjiqi[index1]=true;
     visitask[index2]=true;
 }    
   }
 
}
cout<<count<<" "<<sumvalue<<endl;    
return 0;
}

发表于 2019-09-20 14:45:48 回复(0)
这不是一个NP-hard问题么。。😥
发表于 2019-09-02 16:31:01 回复(0)
参考牛客网校招历年名企真题的做法,Java实现
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        Node [] machine=new Node[n];
        Node [] task=new Node[m];

        for (int i=0;i<n;i++){
            Node node=new Node();
            node.setTime(in.nextInt());
            node.setLevel(in.nextInt());
            machine[i]=node;
        }
        for (int i=0;i<m;i++){
            Node node=new Node();
            node.setTime(in.nextInt());
            node.setLevel(in.nextInt());
            task[i]=node;
        }
        // 从收益公式来看,任务的执行时间越长、等级越高,则收益更大
        // 将任务、机器按时间从大到小排序,时间相同时,则按照等级从大到小排序
        Arrays.sort(task, new Comparator<Node>() { @Override public int compare(Node o1, Node o2) {
                if (o1.getTime()==o2.getTime())
                    return o2.getLevel().compareTo(o1.getLevel());
                return o2.getTime().compareTo(o1.getTime());
            }
        });
        Arrays.sort(machine, new Comparator<Node>() { @Override public int compare(Node o1, Node o2) {
                if (o1.getTime()==o2.getTime())
                    return o2.getLevel().compareTo(o1.getLevel());
                return o2.getTime().compareTo(o1.getTime());
            }
        });
        int [] cont=new int[105]; //下标表示等级,等级范围是0-100
        int j=0;
        int num=0;
        long ans=0;
        for (int i=0;i<m;i++){
            //对每个任务进行遍历
            Node taski=task[i];
            //能执行该任务的各个等级的机器的数目
            while(j<n&& machine[j].getTime()>=taski.getTime()){
                cont[machine[j].getLevel()]++; //对任务i,能完成该任务的某等级的机器数+1
                j++;
            }
            for (int level=taski.getLevel();level<=100;level++){
                //尽量用最小的等级机器来执行
                if (cont[level]>0){
                    num++;
                    cont[level]--; //一个机器只能执行一个任务
                    ans+=(200*taski.getTime()+3*taski.getLevel());
                    break;
                }
            }
        }
        System.out.println(num+" "+ans);
    }
    
    static class Node{
        Integer time,level;

        public Integer getTime() {
            return time;
        }

        public void setTime(Integer time) {
            this.time = time;
        }

        public Integer getLevel() {
            return level;
        }

        public void setLevel(Integer level) {
            this.level = level;
        }
    }
}


编辑于 2019-08-18 13:25:21 回复(0)
关键点还是排序,还有就是那个等级100那里需要注意。
发表于 2019-08-13 19:52:16 回复(0)