题解 P1248 【加工生产调度】

沟里郭嘉 · 2019-05-29 18:56:57 · 题解

第一篇蓝题题解 其实这道题就是考的Johnson算法的应用（废话嘛这不是），具体的证明楼上大佬已经给出，蒟蒻只是按照自己的理解打了一遍，试试嘛。

对了，还有一位巨佬（应该是位小姐姐 嘿嘿嘿）在简书上写了一个关于Johnson算法的文章，很有助于理解。大家可以去看看。

具体地址如下 404 Not Found

#include <iostream>
#include <algorithm>
using namespace std;

5truct Node
{
    int a1, b1;
    int time; //time=1 a1>a2  为什么使用这个time？
    int minn; //其实在后面的cmp函数中可以看到，我利用了
                  // sort去按照time=1和2进行了排序
    int order;//而作为bool类型的time是无法使用sort进行排序的
          //所以。。。我使用int time=1或2;来代替“是”和“否”这两种情况

}; //我们可以利用struct。。。可以把所要用的东西放在一起，减少思维记忆量。。。（其实就是懒）（大雾）

inline bool cmp(Node a,Node b)
{
    if (a.time != b.time)
    {
        return (a.time < b.time);
    }
    else if (a.time == 1)
    {
        return (a.a1 < b.a1);
    }

    return (a.b1 > b.b1);
}//很好理解对吧(弥天大雾)

Node st[100o1];

int main()
{
    int n;
    cin>>n;

    for (int i=1;i<=n;i++)
    {
        cin>>st[i].a1;
        st[i].order=i;
    }

    for (int i=1;i<=n;i++)
    {
        cin>>st[i].b1;
    }

    for (int i=1;i<=n;i++)
    {
        st[i].minn= min(st[i].a1, st[i].b1);

        if(st[i].minn==st[i].a1)
        {
            st[i].time=1;
        }
        else
        {
            st[i].time=2;// 对time进行处理
        }
    }

    sort(st+1, st+1+n, cmp);

    long long ta= st[1].a1, tb= st[1].b1+ta;

    for (int i=2;i<=n;i++)
    {
        ta+=st[i].a1;
        tb=max(ta,tb)+st[i].b1;//模拟求和，很简单（伸手不见五指雾）
    }

    cout<<tb;
    cout<<endl;
    for(int i=1;i<=n;++)
    {
        cout<<st[i].order<<" ";
    }

    return o;
}

感谢大家的观看♪(･ω･)ﾉ

欢迎大家指出我的错误（确实有哦）