[HNOI2011]任务调度

题目描述

有 N 个任务和两台机器 A 与 B。每个任务都需要既在机器 A 上执行,又在机器 B 上执行,

第 i 个任务需要在机器 A 上执行时间 Ai,且需要在机器 B 上执行时间 Bi。最终的目标是所有任务在 A 和 B 上都执行完,且希望执行完所有任务的总时间尽量少。当然问题没有这么简单,有些任务对于先在机器 A 上执行还是先在机器 B 上执行有一定的限制。据此可将所有任务分为三类:

  1. 任务必须先在机器 A 上执行完然后再在机器 B 上执行。

  2. 任务必须先在机器 B 上执行完然后再在机器 A 上执行。

  3. 任务没有限制,既可先在机器 A 上执行,也可先在机器 B 上执行。

现在给定每个任务的类别和需要在机器A和机器B上分别执行的时间,问使所有任务都能按

规定完成所需要的最少总时间是多少。

输入输出格式

输入格式:

从文件input.txt中读入数据,输入文件的第一行只有一个正整数N(1≤N≤20),表示任务的个数。接下来的N行,每行是用空格隔开的三个正整数Ti,
Ai, Bi(1≤Ti≤3, 1≤Ai, Bi≤1000),分别表示第i个任务的类别(类别1, 2,
3的定义如上)以及第i个任务需要在机器A和机器B上分别执行的时间。

输出格式:

输出文件 output.txt 仅包含一个正整数,表示所有任务都执行完所需要的最少总时

输入输出样例

输入样例#1:
复制
3
3 5 7
1 6 1
2 2 6
输出样例#1: 复制
14

说明

样例解释:一种最优任务调度方案为:机器A上执行的各任务依次安排如下:任务1(0 - 5), 任务2(5 - 11), 任务3(11 - 13);机器B上执行的各任务依次安排如下:任务3(0 - 6), 任务 1(6 - 13), 任务2(13 - 14),这样,所有任务都执行完所需要的总时间为14。

先用搜索枚举出第3类,分别分到1或2类

然后排序贪心

对于先要在a机器上运行的任务以需要在b机器上运行时间作为第一关键字,在a机器上运行时间作为第二关键字排序(为什么那种b机器上耗时比较多的放在最后面可能会让b机器运行很久)

但这只有90分,贪心并不一定正确

于是可以随机算法,每次随机交换1类两个元素和2类两个元素,看答案是否更优

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
using namespace std;
struct ZYYS
{
int a,b;
}A[],B[],C[],AA[],BB[];
int cntb,cnta,cntc,ans,t,n;
bool cmpa(ZYYS u,ZYYS v)
{
if (u.a==v.a) return u.b<v.b;
return u.a>v.a;
}
bool cmpb(ZYYS u,ZYYS v)
{
if (u.b==v.b) return u.a<v.a;
return u.b>v.b;
}
int cal()
{int ta,tb,res,i;
ta=;tb=;
for (i=;i<=cntb;i++)
tb+=BB[i].b;
for (i=;i<=cnta;i++)
{
ta+=AA[i].a;
if (ta<tb) tb+=AA[i].b;
else tb=ta+AA[i].b;
}
res=tb;
ta=;tb=;
for (i=;i<=cnta;i++)
ta+=AA[i].a;
for (i=;i<=cntb;i++)
{
tb+=BB[i].b;
if (tb<ta) ta+=BB[i].a;
else ta=tb+BB[i].a;
}
res=max(res,ta);
return res;
}
void check()
{int i,tmp,a1,a2,b1,b2;
for (i=;i<=cnta;i++)
AA[i]=A[i];
for (i=;i<=cntb;i++)
BB[i]=B[i];
sort(AA+,AA+cnta+,cmpb);
sort(BB+,BB+cntb+,cmpa);
tmp=cal();
ans=min(ans,tmp);
for (i=;i<=t;i++)
{
if (cnta)
{
a1=rand()%cnta+,a2=rand()%cnta+;
if (a1==a2) a2=rand()%cnta+;
swap(AA[a1],AA[a2]);
}
if (cntb)
{
b1=rand()%cntb+,b2=rand()%cntb+;
if (b1==b2) b2=rand()%cntb+;
swap(BB[b1],BB[b2]);
}
tmp=cal();
if (tmp<=ans) {ans=tmp;continue;}
if (cnta)swap(AA[a1],AA[a2]);
if (cntb)swap(BB[b1],BB[b2]);
}
}
void dfs(int x)
{
if (x>cntc)
{
check();
return;
}
cnta++;A[cnta]=C[x];
dfs(x+);
cnta--;
cntb++;B[cntb]=C[x];
dfs(x+);
cntb--;
}
int main()
{int i,x,y,opt;
cin>>n;
srand(time());
for (i=;i<=n;i++)
{
scanf("%d",&opt);
scanf("%d%d",&x,&y);
if (opt==)
{
A[++cnta].a=x;A[cnta].b=y;
}
else if (opt==)
{
B[++cntb].a=x;B[cntb].b=y;
}
else C[++cntc].a=x,C[cntc].b=y;
}
t=;
ans=2e9;
dfs();
cout<<ans;
}
上一篇:你不知道的Google控制台


下一篇:Beta冲刺五