Luogu [P1248] 加工生产调度
2024-10-21 13:44:26
这个题可以贪心
我们首先想:对于所有产品,我们大致可以将其分为三类:
①.在A车间的时间要比B车间长。
②.两者一样。
③.在B车间的时间要比A车间长。
对于这三大类,怎么安排顺序?
可以看出,①类是消耗B车间任务,③类是给B车间增加任务。
我们想,要想时间最快,必须要尽可能的让AB两车间没有空闲的工作。如果我们将①放在了开头,而③放在了结尾,那必然会导致开始时B工作的时间断断续续,最后等A工作完了,B还剩下一大堆任务。
所以我们要尽可能的将③放在开始,①放在结尾,②安排在中间就可以(没有什么影响)。
三大类排好顺序后,我们再想每一类内部之间的顺序:
对于①:放在结尾执行,到最后必然A全部执行完毕,B还剩一点没执行(因为A最后执行的产品刚刚归入B类),那我们此时所消耗的时间就是最后产品的B车间时间,当然是越小越好,所以③类要按照B从大到小排。
对于②:好像既然放在了中间,就无所谓了。
对于③:同①理,放在开始执行,一开始必然第一个任务执行A时,B此时空着,那我们此时所消耗的时间就是开始产品的A车间时间,当然是越小越好,所以①类要按照A从小到大排。
然后从头到尾模拟一遍就行了。
代码:
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int n;
struct qwq{
int A;
int B;
int C;//看看这个零件属于哪一类
int id;//此零件下标
}e[];
int cmp(qwq &a,qwq &b){
if(a.C!=b.C)
return a.C>b.C;
else if(a.C==)
return a.A<b.A;
else if(a.C==-)
return a.B>b.B;
else
return a.A<b.A;
}
inline int read(){
int x=;
char ch=getchar();
while(ch<''||ch>'')
ch=getchar();
while(ch>=''&&ch<=''){
x=(x<<)+(x<<)+(ch^);
ch=getchar();
}
return x;
}
int Time_c,cha;
int main(){
n=read();
for(int i=;i<=n;i++)
e[i].A=read(),e[i].id=i;
for(int i=;i<=n;i++){
e[i].B=read();
e[i].C=((e[i].B-e[i].A) >= ? ((e[i].B-e[i].A) > ? : ) : -);//三目运算符给任务分类
}
sort(e+,e+n+,cmp);
for(int i=;i<=n;i++){//模拟
Time_c+=e[i].A;
cha=max(cha-e[i].A,);
cha+=e[i].B;
}
cout<<Time_c+cha<<endl;
for(int i=;i<=n;i++)
printf("%d ",e[i].id);
return ;
}
最新文章
- LBS基站数据解析接口
- 忙了好一阵,今天随便写篇关于canvas的小东西
- dede各种运用[转]
- Mysql 作业(Scheduler)
- Spring的配置文件
- ajaxfileupload.js 文件上传
- 0当执行游戏xc000007b错误的解决方法
- Javascript parseFloat、parseDouble类型转换,数值加减,四舍五入
- Java的家庭记账本程序(K)
- 阿里云主机Nginx下配置NodeJS、Express和Forever
- Linux命令行使用
- Java设计模拟菜单
- ESXi安装实录
- 简单实现Java的RMI——远程方法调用
- gravitee-gateway 又一个开源 apigateway
- grep 详解
- ueditor 定制工具栏图标
- Ubuntu 10.04 下载android 4.1.1_r4
- 【PHPmailer】发送邮件(以163邮箱为例)
- 初学bind
热门文章
- Angular输入框内按下回车会触发其它button的点击事件的解决方法
- Jmeter 线程组、运行次数参数化(转)Jpara1=4 -Jpara2=5
- HDU 2103 Family Plan
- ng2学习--pipe使用
- 牛客假日团队赛1 J.分组
- spark_20180328
- python排序(冒泡、直接选择、直接插入等)
- 解决 This application requires Java Runtime Environment XX
- 【ACM】最少乘法次数 - 树
- python学习二(文件与异常)