NC20087. [HNOI2011]任务调度
描述
有 N 个任务和两台机器 A 与 B。每个任务都需要既在机器 A 上执行，又在机器 B 上执行，第 i 个任务需要在机器 A 上执行时间 Ai，且需要在机器 B 上执行时间 Bi。最终的目标是所有任务在 A 和 B 上都执行完，且希望执行完所有任务的总时间尽量少。当然问题没有这么简单，有些任务对于先在机器 A 上执行还是先在机器 B 上执行有一定的限制。据此可将所有任务分为三类：
任务必须先在机器 A 上执行完然后再在机器 B 上执行。
任务必须先在机器 B 上执行完然后再在机器 A 上执行。
任务没有限制，既可先在机器 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
输出:
14
说明:
样例解释：一种最优任务调度方案为：机器A上执行的各任务依次安排如下：任务1(0 - 5), 任务2(5 - 11), 任务3(11 - 13)；机器B上执行的各任务依次安排如下：任务3(0 - 6), 任务 1(6 - 13), 任务2(13 - 14)，这样，所有任务都执行完所需要的总时间为14。C++14(g++5.4) 解法, 执行用时: 11ms, 内存消耗: 504K, 提交时间: 2020-03-26 16:54:56
#include<bits/stdc++.h>
using namespace std;
const int maxn = 30;
struct Node{
int a, b;
} A[maxn], B[maxn], C[maxn], AA[maxn], BB[maxn];
int ca, cb, cc, N, t, ans;
bool cmpa(const Node &lhs, const Node &rhs){
return lhs.b > rhs.b ||(lhs.b == rhs.b && lhs.a < rhs.a);
}
bool cmpb(const Node &lhs, const Node &rhs){
return lhs.a > rhs.a ||(lhs.a == rhs.a && lhs.b < rhs.b);
}
int getans(){
int sa = 0, sb = 0, ret;
for(int i = 0; i < ca; ++i) sa += AA[i].a;
for(int i = 0; i < cb; ++i){
sb += BB[i].b;
if(sb < sa) sa += BB[i].a;
else sa = sb + BB[i].a;
}
ret = sa;
sa = sb = 0;
for(int i = 0; i < cb; ++i) sb += BB[i].b;
for(int i = 0; i < ca; ++i){
sa += AA[i].a;
if(sa < sb) sb += AA[i].b;
else sb = sa + AA[i].b;
}
return max(sb, ret);
}
void calc(){
int tmp, a1, a2, b1, b2;
for(int i = 0; i < ca; ++i) AA[i] = A[i];
for(int i = 0; i < cb; ++i) BB[i] = B[i];
sort(AA, AA+ca, cmpa);
sort(BB, BB+cb, cmpb);
ans = min(ans, getans());
for(int i = 0; i < 200; ++i){
if(ca){
a1 = rand()%ca, a2 = rand()%ca;
//while(a1 == a2) a1 = rand()%ca, a2 = rand()%ca;
swap(AA[a1], AA[a2]);
}
if(cb){
b1 = rand()%cb, b2 = rand()%cb;
//while(b1 == b2) b1 = rand()%cb, b2 = rand()%cb;
swap(BB[b1], BB[b2]);
}
tmp = getans();
if(tmp < ans){ ans = tmp; continue; }
if(ca) swap(AA[a1], AA[a2]);
if(cb) swap(BB[b1], BB[b2]);
}
}
void dfs(int i){
if(i == cc){
calc();
return;
}
A[ca++] = C[i];
dfs(i+1);
ca--;
B[cb++] = C[i];
dfs(i+1);
cb--;
}
int main(){
scanf("%d", &N);
for(int i = 0; i < N; ++i){
scanf("%d", &t);
if(t == 1){
scanf("%d %d", &A[ca].a, &A[ca].b);
ca++;
}
else if(t == 2){
scanf("%d %d", &B[cb].a, &B[cb].b);
cb++;
}
else{
scanf("%d %d", &C[cc].a, &C[cc].b);
cc++;
}
}
ans = 50000;
dfs(0);
printf("%d\n", ans);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 11ms, 内存消耗: 488K, 提交时间: 2020-03-28 20:22:18
#include<bits/stdc++.h>
using namespace std;
const int maxn=30;
struct Node
{
int a,b;
}A[maxn],B[maxn],C[maxn],AA[maxn],BB[maxn];
int ca,cb,cc,N,t,ans;
bool cmpa(const Node &lhs,const Node &rhs)
{
return lhs.b>rhs.b||(lhs.b==rhs.b&&lhs.a<rhs.a);
}
bool cmpb(const Node &lhs,const Node &rhs)
{
return lhs.a>rhs.a||(lhs.a==rhs.a&&lhs.b<rhs.b);
}
int getans()
{
int sa=0,sb=0,ret;
for(int i=0;i<ca;++i)
sa+=AA[i].a;
for(int i=0;i<cb;++i)
{
sb+=BB[i].b;
if(sb<sa) sa+=BB[i].a;
else sa=sb+BB[i].a;
}
ret=sa;
sa=sb=0;
for(int i=0;i<cb;++i)
sb+=BB[i].b;
for(int i=0;i<ca;++i)
{
sa+=AA[i].a;
if(sa<sb) sb+=AA[i].b;
else sb=sa+AA[i].b;
}
return max(sb,ret);
}
void calc()
{
int tmp,a1,a2,b1,b2;
for(int i=0;i<ca;++i)
AA[i]=A[i];
for(int i=0;i<cb;++i)
BB[i]=B[i];
sort(AA,AA+ca,cmpa);
sort(BB,BB+cb,cmpb);
ans=min(ans,getans());
for(int i=0;i<200;++i)
{
if(ca)
{
a1=rand()%ca,a2=rand()%ca;
swap(AA[a1],AA[a2]);
}
if(cb)
{
b1=rand()%cb,b2=rand()%cb;
swap(BB[b1],BB[b2]);
}
tmp=getans();
if(tmp<ans)
{
ans=tmp;
continue;
}
if(ca)
swap(AA[a1],AA[a2]);
if(cb)
swap(BB[b1],BB[b2]);
}
}
void dfs(int i)
{
if(i==cc)
{
calc();
return;
}
A[ca++]=C[i];
dfs(i+1);
ca--;
B[cb++]=C[i];
dfs(i+1);
cb--;
}
int main()
{
scanf("%d",&N);
for(int i=0;i<N;++i)
{
scanf("%d",&t);
if(t==1)
{
scanf("%d %d",&A[ca].a,&A[ca].b);
ca++;
}
else if(t==2)
{
scanf("%d %d",&B[cb].a,&B[cb].b);
cb++;
}
else
{
scanf("%d %d",&C[cc].a,&C[cc].b);
cc++;
}
}
ans=50000;
dfs(0);
printf("%d\n",ans);
return 0;
}