贪心算法

工厂机器安排算法求助

最近做了一道pta的题,我的思路感觉没有问题。但就是通不过,在网上找到一个和我思路一样的解法,请大家帮忙看看我的算法错在哪里。

题目

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

我的思路

先把机器和任务结构体数组排个序,先优先按xi从大到小,在考虑yi.因为xi要乘以500,比重大。把任务比重大的给它安排时,不能随便的安排一个机器,需要先在时间条件满足情况下,选择等级符合条件,且等级最小的这些机器,则会等级大的机器先被查询,可以安排更多的任务。

我的代码

/*
  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;
  vector<temple> machine(N), task(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;
    }
    task[i].xi = xi;
    task[i].yi = yi;
  }
  sort(task.begin(), task.end(), cmp);
  for (int i = 0; i < task.size(); i++) {
    for (int j = machine.size() - 1; j >= 0; j--) {
      if (machine[j].flag == false) {
        if (machine[j].xi >= task[i].xi && machine[j].yi >= task[i].yi) {
          task[i].flag = true;
          machine[j].flag = true;
          break;
        }
      }
    }
  }
  for(auto temp:task){
    if(temp.flag){
      ans_a+=1;
      ans_b+=500*temp.xi+2*temp.yi;
    }
  }
  cout<<ans_a<<" "<<ans_b;
  system("pause");
}
image 82

不知道错在哪里。

网上的代码

#include <algorithm>
#include <iostream>
#include <vector>
#include<stdio.h>
#include<cstring>
using namespace std;
typedef struct good
{
    int x,y;
}good;
good mach[100005],task[100005];
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++)
         scanf("%d%d",&task[i].x,&task[i].y);
        sort(mach,mach+n,comp);
        sort(task,task+m,comp);
        num=0; sum=0; //完成任务个数,收益 
        int j=0;
        for(int i=0;i<m;i++)
        {
            while(j<n&&mach[j].x>=task[i].x) level[mach[j++].y]++;//在机器中找先找时间大于任务时间的,把这些机器位置记录下来 
            for(int lev=task[i].y; lev<=100;lev++)//在上面记录机器中,再找>=任务等级 ,选机器任务等级符合要求最小的那个 
             if(level[lev])
             {
                 num++; 
                 sum+=500*task[i].x+2*task[i].y; 
                 level[lev]--;
                 break;
             }
        }
        cout<<num<<' '<<sum<<endl;
    }
}
image 83

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

  1. 机器的排序有些问题。你不能保证后一个机器能完成的任务前面的机器就一定能完成。例如我给出以下两个机器(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/

发表评论