今天是一个开心的日子，不禁因为
全新的博客编辑器CuteEditor令人倍感清爽，还因为我第一次用随机算法做的题，竟然一次AC
~~这条题的通过率只有:149/1237
»12.0% 哦~
这道题便是北大ACM上最近这次月赛的
Washing Clothes啦，题目大意是两公婆一齐洗一堆衣服（件数n<100），每件衣服需要洗的时间是不同的，一件衣服只能由一个人来洗，一个人在只能洗完一件衣服后才能洗另外一件衣服，问他俩最少要用多长时间才能把衣服洗完。
这道题一看便知道是NP难的题目——经典的0-1背包问题的变种，由于规模高达100，用常规的确定型解法（搜索、动规等）复杂度高达2100。因此我决定构造一个随机算法。
我的算法大致如下：
1
先求出洗完所有衣服的总时间sum及其一半target；
2先假设所有衣服都是老公洗的，即husbandsum=sum,wifesum=0;
3循环括号中步骤T次：（本题我设T为10000）
4
{
5
若老公洗的衣服所花时间比老婆长，老婆随机地从老公那里拿一件衣服来洗；
6若老婆洗的衣服所花时间比老公长，老公随机地从老婆那里拿一件衣服来洗；
7若老公洗的衣服所花时间刚好为target，则直接跳出循环；
8
}
9在循环中记录最接近target的那次老公所用的时间mi；
10于是洗衣服的总时间则为max(mi,sum-mi)
执行如此恩爱的随机算法后，你就可以得到你想要的AC了~~
附，程序源代码：
程序源代码
1//处女随机题：1AC~~ ^_^
2//2053229 cockerel 3211 Accepted 72K 187MS G++ 1170B 2007-04-02 00:14:59
3#include<cstdio>
4#include<cstring>
5#include<ctime>
6#include<cstdlib>
7#include<cmath>
8#define Ms(a,c) (memset(a,c,sizeof(a)))
9#define max(a,b) (a>b?a:b)
10int a[10][100],c[10];
11int bk[100],bc;
12char clr[10][11];
13int ot[100];
14char oc[100][11];
15const int T=10000;
16int main(){
17 int i,j,k,n,m;
18 srand(time(NULL));
19
while(scanf("%d %d",&m,&n),n!=0){
20 Ms(c,0);
21 for(i=0; i<m; ++i) scanf("%s",clr[i]);
22 for(i=0; i<n; ++i){
23 scanf("%d %s",&ot[i],oc[i]);
24 for(j=0; strcmp(clr[j],oc[i])!=0; ++j);
25 a[j][c[j]++]=ot[i];
26
}
27 int sum=0,csum,rsum,target;
28 for(i=0; i<m; ++i){
29 int *r=a[i],rc=c[i];
30 csum=0;
31 for(j=0; j<c[i]; ++j) csum+=r[j];
32 rsum=csum;
33 target=csum/2;
34 bc=0;
35 int mi=csum;
36 for(j=0; j<T; ++j){
37 if(abs(rsum-target)<abs(mi-target))
38 mi=rsum;
39 if(rsum>target){ //随机将r[k]放到bk去
40 k=rand()%rc;
41 rsum-=r[k];
42 bk[bc++]=r[k];
43 r[k]=r[--rc];
44 }else if(rsum<target){ //随机将bk[k]放到r去
45 k=rand()%bc;
46 rsum+=bk[k];
47 r[rc++]=bk[k];
48 bk[k]=bk[--bc];
49 }else break; //刚好平均
50 }
51 sum+=max(mi,csum-mi);
52 }
53 printf("%d\n",sum);
54 }
55 return 0;
56}
57
注：我做那题时题目并没有说明洗每件衣服的时间上限。
posted on 2007-04-02 12:20
踏雪赤兔 阅读(1647)
评论(12) 编辑 收藏 引用 所属分类:
玩转编程