LOJ#10003 加工生产调度(贪心)
程序员文章站
2022-03-25 17:27:01
...
题解:贪心策略始终是一个比较烦人的地方……容易出错。
这道题因为必须先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;
}
上一篇: 【OpenCV学习笔记】之访问图像的像素与ROI感兴趣区域选取
下一篇: 编译precomp