欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LOJ#10003 加工生产调度(贪心)

程序员文章站 2022-03-25 17:27:01
...

LOJ#10003 加工生产调度(贪心)

LOJ#10003 加工生产调度(贪心) 

题解:贪心策略始终是一个比较烦人的地方……容易出错。

这道题因为必须先a再b,所以第一个在a加工的产品的a值必须尽可能小,这样能减少机器B的等待时间,最后一个在B加工的零件的b值必须尽可能小,这样减少机器A的等待时间。

按照每个产品a值和b值的最小值从小到大排序,如果最小值是a的话就把这个产品往前放,否则往后放。

这题有个比较容易错的地方是最少加工时间= =应该考虑排好序后机器A的工作时间和机器B的工作时间,然后取最大值。

 

AC代码:

#include <iostream>
#include <algorithm>

using namespace std;

struct node
{
    int a, b;
    int p;
    int w;
}st[1005];

int n;
int ta, tb;
int ans[1005];

bool cmp(node a, node b)
{
    return a.w<b.w;
}

int main()
{
    int a=0, b=0;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>st[i].a;
        a+=st[i].a;
        st[i].p=i+1;
    }
    for(int i=0; i<n; i++)
    {
        cin>>st[i].b;
        st[i].w=min(st[i].a, st[i].b);
        b+=st[i].b;
    }
    sort(st, st+n, cmp);
    int left, right;
    left=0;
    right=n-1;
    for(int i=0; i<n; i++)
    {
        if(st[i].w==st[i].a)
        {
            if(left==0) b+=st[i].a;
            ans[left]=st[i].p;
            left++;
        }
        else
        {
            if(right==n-1) a+=st[i].b;
            ans[right]=st[i].p;
            right--;
        }
    }
    cout<<max(a, b)<<endl;
    for(int i=0; i<n-1; i++)
    {
        cout<<ans[i]<<' ';
    }
    cout<<ans[n-1]<<endl;
    return 0;
}