51Nod - 1205 （流水先调度）超级经典的贪心模板题

题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1205

N个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为aii和bii。你可以安排每个作业的执行顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。求这个最少的时间。

Input第1行：1个数N，表示作业的数量。(2 <= N <= 50000)
第2 - N + 1行：每行两个数，中间用空格分隔，表示在M1和M2上加工所需的时间aii, bii。（1 <= aii, bii <= 10000)。Output输出完成所有作业所需的最少时间。Sample Input

Sample Output

14

分析：
思路：Johnson算法：
1：将任务分为两类，A类任务t1<t2，B类任务t1>=t2
2：两类任务分别排序，其中A类按 t1 递增排序，B类按 t2 递减排序
3：合并两类，将第二类任务接到第一类任务后面，此时任务的顺序最佳
4：遍历所有任务，计算总耗时

比如样例排序好之后是：
A:3 7
B:4 2
C:2 1
D:1 1 
先在机器1完成A的3，然后在机器1进行B的4时，同时在机器2进行A的7，然后在机器1进行C的2，然后在机器1进行D的1，这段时间机器2都是
被A的7占领的，所以答案是：3+7+2+1+1=14

code：

#include<stdio.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <queue>

#include<string.h>

using namespace std;

#define max_v 50005

struct node

{

    int x,y;

}p[max_v],pp[max_v];

bool cmp1(node a,node b)

{

    return a.x<b.x;

}

bool cmp2(node a,node b)

{

    return a.y>b.y;

}

int f[max_v];

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        int len1=,len2=;

        int x,y;

        for(int i=;i<n;i++)

        {

            scanf("%d %d",&x,&y);

            if(x<y)

            {

                p[len1].x=x;

                p[len1++].y=y;

            }else

            {

                pp[len2].x=x;

                pp[len2++].y=y;

            }

        }

        sort(p,p+len1,cmp1);

        sort(pp,pp+len2,cmp2);

        for(int i=len1;i<len1+len2;i++)

        {

            p[i]=pp[i-len1];

        }

        for(int i=;i<len1+len2;i++)

        {

            printf("%d %d\n",p[i].x,p[i].y);

        }

        printf("\n");

        f[]=p[].x;

        for(int i=;i<n;i++)

        {

            f[i]=f[i-]+p[i].x;

        }

        for(int i=;i<n;i++)

        {

            printf("%d ",f[i]);

        }

        printf("\n\n");

        int sum=;

        for(int i=;i<n;i++)

        {

            if(sum>=f[i])

            {

                sum+=p[i].y;

            }else

            {

                sum=f[i]+p[i].y;

            }

        }

        printf("%d\n",sum);

    }

    return ;

}

巴特西

51Nod - 1205 （流水先调度）超级经典的贪心模板题

最新文章

热门文章

巴特西

51Nod - 1205 （流水先调度）超级经典的贪心 模板题

最新文章

热门文章

51Nod - 1205 （流水先调度）超级经典的贪心模板题