http://docs.google.com/gview?a=v&q=cache:Up-jSb3wqOAJ:www.cs.dartmouth.edu/~doug/mdmspe.pdf
posted @
2009-07-26 14:38 wyiu 阅读(84) |
评论 (0) |
编辑 收藏
#define M 10000
bool prime[M];
int pri[M];
void prime()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
//1表示不是素数,0表示是素数
//memset(prime,0,sizeof(prime));
int i,j,
k=0;
prime[0]=prime[1]=1;
for(i=2;i<M;i++)
if(prime[i]==0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
//pri[k++]=i;
for(j=2*i;j<M;j+=i)
prime[j]=1;
}
}
posted @
2009-07-26 10:39 wyiu 阅读(172) |
评论 (0) |
编辑 收藏
筛个素数表+BFS
貌似数据里没有impossible的情况
#include<iostream>
using namespace std;
#define M 10000
bool prime[M];
bool visit[M];
int s,e;
int step;
void crearprimetable()//筛素数表
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j;
//prime[0]=prime[1]=1;
for(i=2;i<M;i++) //判断i是不是素数
if(prime[i]==0) //是
for(j=i+i;j<M;j+=i) //把是i倍数的数j记上1,不是素数.
prime[j]=1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void bfs()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j,k,num,t;
int que[10000];
int front,rear,trear;
step=0;
if(s==e) return ;
front=rear=0;
que[rear++]=s;
while(front<rear)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
step++;
trear=rear;
while(front<trear)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
num=que[front++];
for(i=1;i<10;i++)//换个位
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
t=num/10*10+i;
if(!prime[t] && !visit[t])
if(t==e) return ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{que[rear++]=t;visit[t]=true;}
}
for(i=0;i<10;i++)//换十位
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
t=num/100*100+i*10+num%10;
if(!prime[t] && !visit[t])
if(t==e) return ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{que[rear++]=t;visit[t]=true;}
}
for(i=0;i<10;i++)//换百位
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
t=num/1000*1000+i*100+num%100;
if(!prime[t] && !visit[t])
if(t==e) return ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{que[rear++]=t;visit[t]=true;}
}
for(i=1;i<10;i++)//换百位
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
t=i*1000+num%1000;
if(!prime[t] && !visit[t])
if(t==e) return ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{que[rear++]=t;visit[t]=true;}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int n;
crearprimetable();
scanf("%d",&n);
while(n--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d%d",&s,&e);
memset(visit,0,sizeof(visit));
bfs();
printf("%d\n",step);
}
return 0;
}
posted @
2009-07-23 16:27 wyiu 阅读(163) |
评论 (0) |
编辑 收藏
//模拟洗牌,不知道为什么分类是bfs
#include<iostream>
using namespace std;
char s1[101];
char s2[101];
char s12[201];//每次洗牌后的串
char s[201]; //目标串
char first[201];//第一次洗牌后的串
int n,len,len2;
int step;
void shuf()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j;
step=1;
while(step)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(i=0,j=0;i<len;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
s12[j++]=s2[i];
s12[j++]=s1[i];
}
len2=j;
if(step==1) strcpy(first,s12);
if(strcmp(s,s12)==0) return ;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(step!=1 && strcmp(s12,first)==0)
{ step=-1;return ;}
for(j=0;j<len;j++)
s1[j]=s12[j];
for(;j<len2;j++)
s2[j-len]=s12[j];
step++;
}
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j,k;
scanf("%d",&n);
for(k=1;k<=n;k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
memset(s,0,sizeof(s));
memset(first,0,sizeof(first));
memset(s12,0,sizeof(s12));
scanf(" %d %s %s %s",&len,&s1,&s2,&s);
shuf();
if(step==-1) printf("%d -1\n",k);
else printf("%d %d\n",k,step);
}
return 0;
}
posted @
2009-07-23 15:12 wyiu 阅读(194) |
评论 (0) |
编辑 收藏
//菜鸟做法,BFS,n==99,内存空间无敌的大...
#include<iostream>
using namespace std;
//usig64_18,446,744,073,709,551,615_20wei
__int64 que[800000];
__int64 n;
__int64 t;
__int64 bfs()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int front=0,rear=0;
que[rear++]=1;
while(front<rear)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
t=que[front++];
t*=10;
if(t%n==0) return t;
que[rear++]=t;
t+=1;
if(t%n==0) return t;
que[rear++]=t;
}
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
while(scanf("%I64d",&n)!=EOF && n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("%I64d\n",bfs());
}
return 0;
}
posted @
2009-07-23 13:57 wyiu 阅读(457) |
评论 (0) |
编辑 收藏
这题想起魔方了,改改A了2225
#include<iostream>
using namespace std;
char dung[35][35][35];
bool visit[35][35][35];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dx[6]=
{-1,0,0,0,0,1};
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dy[6]=
{0,-1,0,0,1,0};
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dz[6]=
{0,0,-1,1,0,0};
int que[82000];//3*30*30*30,一开始开得太小了
2700,27000,30000,40000,50000,640000全TM的WA||RE
int L,R,C;
int sx,sy,sz,ex,ey,ez;
int step;
void bfs()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,x,y,z,tx,ty,tz;
int rear,front,trear;
bool reach=false;
memset(que,0,sizeof(que));
rear=front=0;
que[rear++]=sx;
que[rear++]=sy;
que[rear++]=sz;
visit[sx][sy][sz]=true;
while(front<rear )//&& !visit[ex][ey][ez])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(visit[ex][ey][ez])
{reach=true;break;}//找到E,停
trear=rear;
step++;
while(front<trear )//&& !visit[ex][ey][ez])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
//if(visit[ex][ey][ez]) {reach=true;break;}
x=que[front++];
y=que[front++];
z=que[front++];
for(i=0;i<6;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
tx=x+dx[i];
ty=y+dy[i];
tz=z+dz[i];
if(tx>=0 && tx<L && ty>=0 && ty<R && tz>=0 && tz<C && !visit[tx][ty][tz] && dung[tx][ty][tz]!='#')
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
visit[tx][ty][tz]=true;
que[rear++]=tx;
que[rear++]=ty;
que[rear++]=tz;
}
}//for
}//while
}//while
if(!reach) step=-1;//找不到E,trapped
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j,k;
while(scanf("%d%d%d",&L,&R,&C)!=EOF && L && R && C)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
memset(visit,0,sizeof(visit));
for(i=0;i<L;i++)
for(j=0;j<R;j++)
scanf(" %s",dung[i][j]);
for(i=0;i<L;i++)
for(j=0;j<R;j++)
for(k=0;k<C;k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(dung[i][j][k]=='S')
{sx=i;sy=j;sz=k;}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else if(dung[i][j][k]=='E')
{ex=i;ey=j;ez=k;}
}
step=0;
bfs();
if(step==-1) printf("Trapped!\n");
else printf("Escaped in %d minute(s).\n",step);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
return 0;
}
posted @
2009-07-23 11:39 wyiu 阅读(557) |
评论 (0) |
编辑 收藏
//很有趣的一题,让我想起口袋怪兽
WA了老半天,原来是两个if()放反了,居然不判RE判WA,o(╯□╰)o
#include<iostream>
using namespace std;
char map[21][21];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dx[4]=
{0,-1,0,1};
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dy[4]=
{-1,0,1,0};
int h,w,sx,sy;
int step;
int res;
void dfs(int x,int y)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int dir,tx,ty;
if(step>=10) return ;
for(dir=0;dir<4;dir++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
tx=x;ty=y;
while(1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
tx=tx+dx[dir]; ty=ty+dy[dir];
if(tx<0 || tx>=h || ty<0 || ty>=w )break;
if(map[tx][ty]=='3')
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
step++;
//printf("--%d--\n",step);
if(res>step) res=step;
step--;
return ;
}
else
if(map[tx][ty]=='1')
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
tx=tx-dx[dir];ty=ty-dy[dir];
if(tx!=x || ty!=y)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
map[tx+dx[dir]][ty+dy[dir]]='0';
step++;
dfs(tx,ty);
step--;
map[tx+dx[dir]][ty+dy[dir]]='1';
}
break;
}
}//while
}//for
}//dfs
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j;
while(scanf("%d%d",&w,&h)!=EOF && w)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
step=0;
for(i=0;i<h;i++)
for(j=0;j<w;j++)
scanf(" %c",&map[i][j]);
for(i=0;i<h;i++)
for(j=0;j<w;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(map[i][j]=='2')
{sx=i;sy=j;break;}
res=9999999;
dfs(sx,sy);
if(res>10) printf("-1\n");
else printf("%d\n",res);
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted @
2009-07-22 23:46 wyiu 阅读(991) |
评论 (10) |
编辑 收藏
//解释转的~~~~~~
『题目大意』
一次比赛中,共M道题,T个队,p[i][j]表示队i解出题j的概率;问每队至少解出一题且
冠军队至少解出N道题的概率。
『算法』
设a[i][j][k]表示第i队在前j道题中共解出k道题的概率,易得a[i][j][k]有如下递推
关系(另需考虑边界条件):
a[i][j][k] = a[i][j-1][k-1] * p[i][j] + a[i][j-1][k] * (1-p[i][j])
设s[i][j]表示a[i][M][0] + a[i][M][1] + ... + a[i][M][j]
问题的解可以转化为:每队均至少做一题的概率(用P1表示)减去每队做题数均在1到N-1
之间的概率(用P2表示)。
P1 = (s[1][M] - s[1][0])*(s[2][M]-s[2][0])*...*(s[T][M]-s[T][0])
P2 = (s[1][N-1] - s[1][0])*(s[2][N-1]-s[2][0])*...*(s[T][N-1]-s[T][0])
『算法复杂度』
O(T*M^2)
『说明』
感谢UESTC的zhucheng在poj的提示!
#include<iostream>
using namespace std;
#define MM 30
#define MT 1000
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
double p[MT+1][MM+1];
double d[MT+1][MM+1][MM+1];
double MTO[MT+1]; //每队至少做出一题的概率
double LTN[MT+1];//少于N道,亦即1
N-1
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j,k;
int M,T,N;
double tmp1,tmp2;
while(scanf("%d%d%d",&M,&T,&N)!=EOF && M)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
memset(MTO,0,sizeof(MTO));
memset(LTN,0,sizeof(LTN));
for(i=1;i<=T;i++)
for(j=1;j<=M;j++)
scanf("%lf",&p[i][j]);
for(i=1;i<=T;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
d[i][0][0]=1;
for(j=1;j<=M;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
d[i][j][0] = d[i][j-1][0]*(1-p[i][j]);
for(k=1;k<=M;k++)
d[i][j][k]=p[i][j]*d[i][j-1][k-1]+(1-p[i][j])*d[i][j-1][k];
}
}
tmp1=tmp2=1.0;
for(i=1;i<=T;tmp1*=MTO[i],i++)
for(k=1;k<=M;k++)
MTO[i]+=d[i][M][k];
for(i=1;i<=T;tmp2*=LTN[i],i++)
for(k=1;k<N;k++)
LTN[i]+=d[i][M][k];
printf("%.3lf\n",tmp1-tmp2);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
附上discuss上一组数据:
10 20 10
0.1 0.9 0.8 1 0.9 0.8 1 0.9 0.8 0.2
1 0.9 0.8 1 0.9 0.8 1 0.9 0.8 0.8
0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.7
0.2 0.23 0.56 0.2 0.23 0.56 0.2 0.23 0.56 0.88
0.56 0.2 0.23 0.56 0.88 0.56 0.2 0.23 0.56 0.88
0.37 0.99 0.12 0.82 0.47 0.37 0.99 0.12 0.82 0.47
0.82 0.47 0.37 0.99 0.12 0.82 0.47 0.37 0.99 0.12
0.37 0.99 0.12 0.82 0.472 0.373 0.99 0.12 0.82 0.47
0.472 0.373 0.99 0.12 0.82 0.472 0.373 0.99 0.12 0.82
0.1 0.9 0.8 1 0.9 0.8 1 0.9 0.8 0.2
1 0.9 0.8 1 0.9 0.8 1 0.9 0.8 0.8
0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.9 0.7
0.2 0.23 0.56 0.2 0.23 0.56 0.2 0.23 0.56 0.88
0.56 0.2 0.23 0.56 0.88 0.56 0.2 0.23 0.56 0.88
0.37 0.99 0.12 0.82 0.47 0.37 0.99 0.12 0.82 0.47
0.82 0.47 0.37 0.99 0.12 0.82 0.47 0.37 0.99 0.12
0.37 0.99 0.12 0.82 0.472 0.373 0.99 0.12 0.82 0.47
0.472 0.373 0.99 0.12 0.82 0.472 0.373 0.99 0.12 0.82
0.56 0.88 0.56 0.2 0.23 0.373 0.99 0.12 0.82 0.472
0.472 0.373 0.99 0.12 0.82 0.82 0.472 0.373 0.99 0.33
结果:0.740
posted @
2009-07-19 17:13 wyiu 阅读(427) |
评论 (1) |
编辑 收藏
#include<iostream>
using namespace std;
#define M 26
bool grap[M+1][M+1];
int squ[M+1];
char equ[M*M][4];
int ind[M+1];
int indcop[M+1];
int cnt,n,m;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int topsort()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j,p,num=0,
flag=0,
now=0;
for(i=0;i<n;i++)
indcop[i]=ind[i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
num=0;
for(j=0;j<n;j++)
if(indcop[j]==0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
num++;
p=j;
}
if(num==0) //有回路
return 0;
if(num>1) //不确定
flag=1;
//return -1; //不确定的情况下还要判断有没回路,o(╯□╰)o
indcop[p]=-1; //置为负值
squ[now++]=p;
for(j=0;j<n;j++) //删除相关的边
if(grap[p][j])
indcop[j]--;
}
if(flag) return -1; //不确定
return 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i,j,ret;
char l,r;
bool done;
while(scanf("%d%d",&n,&m)==2 && n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(i=0;i<m;i++)
scanf(" %s",&equ[i]);
done=false;
memset(ind,0,sizeof(ind));
memset(grap,0,sizeof(grap));
for(i=0;i<m;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
l=equ[i][0];r=equ[i][2];
grap[l-'A'][r-'A']=true;
ind[r-'A']++;
ret=topsort();
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if( ret==0 )
{ printf("Inconsistency found after %d relations.\n",i+1); done=true; break;}
if( ret==1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("Sorted sequence determined after %d relations: ",i+1);
for(j=0;j<n;j++)
printf("%c",'A'+squ[j]);
printf(".\n");
done=true;
break;
}
}
if(!done) printf("Sorted sequence cannot be determined.\n");
}
return 0;
}
posted @
2009-07-13 14:00 wyiu 阅读(189) |
评论 (0) |
编辑 收藏
#include<iostream>
using namespace std;
#define MAXN 500000
int x[MAXN+1];
int z[MAXN+1];
__int64 reverse;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void merge(int low,int mid,int high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i=low,j=mid+1,q=0;
while (i<=mid && j<=high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (x[i]<=x[j])
z[q++]=x[i++];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
z[q++]=x[j++];
reverse+=mid-i+1;
}
}
while (i<=mid)
z[q++]=x[i++];
while (j<=high)
z[q++]=x[j++];
for(i=0;i<q;i++)
x[low+i]=z[i];
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void mergesort(int low,int high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int mid;
if ( low< high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,mid,high);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int n,i;
while(scanf("%d",&n)==1 && n!=0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(i=0;i<n;i++)
scanf("%d",&x[i]);
reverse=0;
mergesort(0,n-1);
printf("%I64d\n",reverse);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
return 0;
}
posted @
2009-07-12 14:59 wyiu 阅读(91) |
评论 (0) |
编辑 收藏