BZOJ 2336 [HNOI2011] 任务调度

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2336

题意：n 个任务，AB 两个机器，每个任务都需要在 A 做一段，B 做一段。有的任务必须先在 A 上做，有的必须先在 B 上做，有的没有限制，问最短时间。

搞了一上午... 始终 WA 一个点，以为掉进了玄学调参的深坑，结果发现是傻逼的忘记初始化 cnt....

我们枚举 (或随机) 没有限制的任务，将它们归入有限制的任务类型，这样就只需要考虑 k=1 和 2 的情况

然后贪心排序，随机交换两个任务，看看是否更优，可能是 bzoj 太水，只交换 20 次也能过 orz

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#define N 1010
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int t[N],a[N],b[N],stk[N],top,ans=100000000;
int s1[N],s2[N],cnt1,cnt2;
int lambda=1000; 
bool cmp1(int i,int j)
{return a[i]<a[j];}
bool cmp2(int i,int j)
{return b[i]<b[j];}
int cal()
{
    int ta=0,tb=0,aans=0;
    for(int i=1;i<=cnt2;i++)tb+=b[s2[i]];
    for(int i=1;i<=cnt1;i++)
    {
        ta+=a[s1[i]];
        if(ta<tb)tb+=b[s1[i]];
        else tb=ta+b[s1[i]];
    }
    aans=tb;
    ta=tb=0;
    for(int i=1;i<=cnt1;i++)ta+=a[s1[i]];
    for(int i=1;i<=cnt2;i++)
    {
        tb+=b[s2[i]];
        if(tb<ta)ta+=a[s2[i]];
        else ta=tb+a[s2[i]];
    }
    aans=max(aans,ta);
    return aans;
}
void work()
{
	cnt1=cnt2=0;
    for(int i=1;i<=n;i++)
    {
        if(t[i]==1)s1[++cnt1]=i;
        else s2[++cnt2]=i;
    }
    sort(s1+1,s1+cnt1+1,cmp1);
    sort(s2+1,s2+cnt2+1,cmp2);
    int now=cal();
	int x1,y1,x2,y2,tmp;
    for(int i=1;i<=lambda;i++)
    {
        if(cnt1){x1=rand()%cnt1+1,y1=rand()%cnt1+1;swap(s1[x1],s1[y1]);}
        if(cnt2){x2=rand()%cnt2+1,y2=rand()%cnt2+1;swap(s2[x2],s2[y2]);}
        tmp=cal();
        if(now>tmp)now=tmp;
        else
        {
            if(cnt1)swap(s1[x1],s1[y1]);
            if(cnt2)swap(s2[x2],s2[y2]);
        }
    }
    ans=min(ans,now);
}
void div(int x)
{
    if(x>top){work();return;}
    t[stk[x]]=1;
    div(x+1);
    t[stk[x]]=2;
    div(x+1);
}
int main()
{
    srand(19260817);
    n=read();
    for(int i=1;i<=n;i++)
    {
        t[i]=read(),a[i]=read(),b[i]=read();
        if(t[i]==3)stk[++top]=i;
    }
    div(1);
    printf("%d",ans);
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#define N 1010

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}

while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

int t[N],a[N],b[N],stk[N],top,ans=100000000;

int s1[N],s2[N],cnt1,cnt2;

int lambda=1000;

bool cmp1(int i,int j)

{return a[i]<a[j];}

bool cmp2(int i,int j)

{return b[i]<b[j];}

int cal()

{

int ta=0,tb=0,aans=0;

for(int i=1;i<=cnt2;i++)tb+=b[s2[i]];

for(int i=1;i<=cnt1;i++)

{

ta+=a[s1[i]];

if(ta<tb)tb+=b[s1[i]];

else tb=ta+b[s1[i]];

}

aans=tb;

ta=tb=0;

for(int i=1;i<=cnt1;i++)ta+=a[s1[i]];

for(int i=1;i<=cnt2;i++)

{

tb+=b[s2[i]];

if(tb<ta)ta+=a[s2[i]];

else ta=tb+a[s2[i]];

}

aans=max(aans,ta);

return aans;

}

void work()

{

cnt1=cnt2=0;

for(int i=1;i<=n;i++)

{

if(t[i]==1)s1[++cnt1]=i;

else s2[++cnt2]=i;

}

sort(s1+1,s1+cnt1+1,cmp1);

sort(s2+1,s2+cnt2+1,cmp2);

int now=cal();

int x1,y1,x2,y2,tmp;

for(int i=1;i<=lambda;i++)

{

if(cnt1){x1=rand()%cnt1+1,y1=rand()%cnt1+1;swap(s1[x1],s1[y1]);}

if(cnt2){x2=rand()%cnt2+1,y2=rand()%cnt2+1;swap(s2[x2],s2[y2]);}

tmp=cal();

if(now>tmp)now=tmp;

else

{

if(cnt1)swap(s1[x1],s1[y1]);

if(cnt2)swap(s2[x2],s2[y2]);

}

ans=min(ans,now);

}

void div(int x)

{

if(x>top){work();return;}

t[stk[x]]=1;

div(x+1);

t[stk[x]]=2;

div(x+1);

}

int main()

{

srand(19260817);

n=read();

for(int i=1;i<=n;i++)

{

t[i]=read(),a[i]=read(),b[i]=read();

if(t[i]==3)stk[++top]=i;

}

div(1);

printf("%d",ans);

}

zgz233

zgz233

BZOJ 2336 [HNOI2011] 任务调度

l1ll5

Comments | NOTHING