题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2336
题意：n 个任务，AB 两个机器，每个任务都需要在 A 做一段，B 做一段。有的任务必须先在 A 上做，有的必须先在 B 上做，有的没有限制，问最短时间。
搞了一上午... 始终 WA 一个点，以为掉进了玄学调参的深坑，结果发现是傻逼的忘记初始化 cnt....
我们枚举 (或随机) 没有限制的任务，将它们归入有限制的任务类型，这样就只需要考虑 k=1 和 2 的情况
然后贪心排序，随机交换两个任务，看看是否更优，可能是 bzoj 太水，只交换 20 次也能过 orz
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#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); } |
Comments | NOTHING