信息学奥赛一本通T1425-加工生产调度

解题思路:

这是一道很经典的题，只需要记住这种题型的一个结论：

       A机器上加工时间短的任务应优先，而在B机器上加工时间短的任务应该排在后面

注意事项:

#include<iostream>

#include<algorithm>

using namespace std;

struct node{

    int id;

    int t;

}m[10000];

int main()

{

    int n;cin>>n;

    int a[10000],b[10000];

    for(int i=1;i<=n;i++)cin>>a[i];

    for(int i=1;i<=n;i++)cin>>b[i];

    for(int i=1;i<=n;i++){m[i].id=i; m[i].t=min(a[i],b[i]);}

    for(int i=1;i<=n-1;i++)         //好像只有选择排序才让过

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

          if(m[i].t>m[j].t)

          {

               swap(m[i].t,m[j].t);

               swap(m[i].id,m[j].id);

          }

    int r=n,l=1;

    int ans[10000];//加工顺序

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

        if(m[i].t==a[m[i].id]){ans[l]=m[i].id;l++;}

        else {ans[r]=m[i].id;r--;}

    }

    int sum1=0,sum2=0;

    for(int i=1;i<=n;i++){              //背诵+记忆

        //还没有加工第i个的第二道程序之前总时间取决于sum1和sum2的最大值

        sum1+=a[ans[i]];

        sum2=max(sum1,sum2);

        //之后在执行第二道工序

        sum2+=b[ans[i]];

    }

    cout<<sum2<<endl;

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

        cout<<ans[i]<<" ";

    }

    cout<<ans[n]<<endl;

    return 0;

}