工厂机器安排算法求助

题目

Today the company has m tasks to complete. The ith task need xi minutes to complete. Meanwhile, this task has a difficulty level yi. The machine whose level below this task’s level yi cannot complete this task. If the company completes this task, they will get (500xi+2yi) dollars.

The company has n machines. Each machine has a maximum working time and a level. If the time for the task is more than the maximum working time of the machine, the machine can not complete this task. Each machine can only complete a task one day. Each task can only be completed by one machine.

The company hopes to maximize the number of the tasks which they can complete today. If there are multiple solutions, they hopes to make the money maximum.

输入格式:

The input contains several test cases.

The first line contains two integers N and M. N is the number of the machines.M is the number of tasks(1 < =N <= 100000,1<=M<=100000).

The following N lines each contains two integers xi(0<xi<1440),yi(0=<yi<=100).xi is the maximum time the machine can work.yi is the level of the machine.

The following M lines each contains two integers xi(0<xi<1440),yi(0=<yi<=100).xi is the time we need to complete the task.yi is the level of the task.

输出格式:

For each test case, output two integers, the maximum number of the tasks which the company can complete today and the money they will get.

输入样例:

1 2
100 3
100 2
100 1


输出样例:

1 50004

我的代码

/*
1.读入机器信息,存入结构体中,设置标志位表示是否占用
2.将机器按时间排序,读入任务信息,不满足条件的不存入,存入结构体,设置标志位表示是否可以完成
2.按任务时间排序,再对机器从小到大查询,看是否满足从大到小的任务,需满足优先级
*/
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct temple {
int xi;
int yi;
bool flag = false;
};

inline int cmp(temple a, temple b) {
if(a.xi==b.xi){
return a.yi>b.yi;
}
return a.xi > b.xi; }

int main() {
int N, M, xi, yi, max_yi=0,ans_a=0;
long ans_b=0;
cin>>N>>M;
for (int i = 0; i < N; i++) {
cin >> machine[i].xi >> machine[i].yi;
if(machine[i].yi>max_yi){
max_yi=machine[i].yi;
}
}
sort(begin(machine), end(machine), cmp);
for (int i = 0; i < M; i++) {
cin >> xi >> yi;
if (yi > max_yi || xi > machine[0].xi) {
continue;
}
}
for (int i = 0; i < task.size(); i++) {
for (int j = machine.size() - 1; j >= 0; j--) {
if (machine[j].flag == false) {
machine[j].flag = true;
break;
}
}
}
}
if(temp.flag){
ans_a+=1;
ans_b+=500*temp.xi+2*temp.yi;
}
}
cout<<ans_a<<" "<<ans_b;
system("pause");
}

网上的代码

#include <algorithm>
#include <iostream>
#include <vector>
#include<stdio.h>
#include<cstring>
using namespace std;
typedef struct good
{
int x,y;
}good;
bool comp(good a,good b)
{
if(a.x==b.x)
return a.y>b.y;
return a.x>b.x;
}
int main()
{
int n,m,num,x,y,level[105];
long sum;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(level,0,sizeof(level));//level用来符合条件的机器位置
for(int i=0;i<n;i++)
scanf("%d%d",&mach[i].x,&mach[i].y);
for(int i=0;i<m;i++)
sort(mach,mach+n,comp);
num=0; sum=0; //完成任务个数，收益
int j=0;
for(int i=0;i<m;i++)
{
if(level[lev])
{
num++;
level[lev]--;
break;
}
}
cout<<num<<' '<<sum<<endl;
}
}

4 thoughts on “工厂机器安排算法求助”

1. Shopkeeper说道：

机器的排序有些问题。你不能保证后一个机器能完成的任务前面的机器就一定能完成。例如我给出以下两个机器(x,y):(3,1)(2,2)，和两个任务(x,y):(2,1)(1,2)，顺序就是你的排序方式。
那么按照你的算法先给(2,2)选任务，它会选择(2,1)，但是剩下来的(3,1)就没有可执行的任务了。但是最优解是(3,1)->(2,1),(2,2)->(1,2)。
可以参考我写的帖子：https://www.cztcode.com/2020/plant-machinery-arrangement-greedy/

1. sugarcane说道：

原来这样，懂了

2. 原来错在这了，可以可以

3. 也就是说，应该根据任务分机器，不能根据机器分任务