算法竞赛入门经典教案第8章高效设计

8 8.4O【安排 例8-1最大连续和。 8-1最大连续和tot=bestA[1];for(i=1;i<=n;i++)for(ji;jn;j++)A[i],…,A[j]intsum=0;for(ki;kj;k++)sum+=A[k];}if(sum> bestsum;}nnnT(n)n

(ji1)

(ni1)(ni2)n(n1)(nnn

8-2：基本操作的数量往往可以写成关于“输入规模”的表达式，保留最大项并提示8-3：确的。尽管如此，如果成功抓住了最主要的运算量所在，算法分析的结果常常十分有用的。n3。这就是“上界分析。上界也有记号：T(n)=O(n3)。提示8-4：在算法设计中，常常不进行精确分析，而是假定各种情况同时取到，8-2最大连续和S[0]=for(i=1;i<=n;i++)S[i]=S[i-1]+for(i=1;i<=n;for(ji;j<=n;j++)if(S[j]-S[i-1]>=best=S[j]-S[i-1];}}S[1],S[2],S[3]…,每个只“nnT(n)

(ni1)n(n2O(n2)。38-3最大连续和（3）（8-1intmaxsum(int*A,intx,inty){inti,m,v,L,R,max;if(y-x==1) returnA[x];//只有一个元素，直接返回m=x+(y-x)/2;//分治第一步：划分成[x,m)和[m,y)maxmaxsum(A,x,m)maxsum(A,m,ymaxsum(A,x,m)：maxsum(A,m,y);v0;LA[m-1];（1）Lfor(i=m-1;i>=x;i--){v+=if(v>L)}v=0;R=A[m]; for(i=m;i<y;i++){v+=if(v> }if(L+R maxL+R;LRreturn}8-1ntotT(n)T(n)=2T(n/2)+n， 也称为有效算法；而n!或者2n这样的低效的算法称为指数时间算法（exponential-time一是本身的精确性；二是对程序实现细节与计算机硬件的依赖性。

n。8-28-4归并排序（从小到大voidmerge_sort(int*A,intx,inty,int*T){if(y-x>1){intm=x+(y-x)/2; intp=x,q=m,i=x;merge_sort(A,x,mT);//递归求解merge_sort(A,m,yT);//递归求解while(p<m||q<y){if(q>=y||(p<m&&A[p]<=A[q]))//从左半数组到临时空T[i++]= //从右半数组到临时空T[i++]=}for(i=x;i<y;i++)A[i]= //从辅助空间到A数}}如果第二个序列为空（此时第一个序列一定非空），A[p]A[p]。 例8-2逆序对数。 给一列a1,a2,…,an，求它的逆序对数，即有多少个有序对(i,j)，使得i<j但ai>aj。np（左边所剩的元素在区间[p,mm-。#includeintA[]=intT[]=voidinverse_pair(int*A,intx,inty,int*cnt,int*T){if(y-x>1){intm=x+(y-x)/2; intp=x,q=m,i=x;inverse_pair(A,x,m,cnt,T);//递归求解inverse_pair(A,m,y,cnt,T);//递归求解while(p<m||q<y){if(q>=y||(p<m&&A[p]<=A[q]))/从左半数组到临时空T[i++]=else T[i++]=*cnt+=m-p; }}for(i=x;i<y; A[i]= //从辅助空间到A数}}intinti,cnt=0;;inverse_pair(A,0,6,&cnt,T);printf("%d\n",cnt);return} 例8-3第k小的数。 （1≤k≤n，O(n)。#include<iostream>#include<cmath>usingnamespacestd;constintN=100;intPartition(inta[Nintlow,inthigh){inti=intj=high+1;intx=a[low];while(a[++i]<while(a[--j]>x);if(i>=j)break;swap(a[i],a[j]);}a[low]=a[j];a[j]=x;returnj;}intSelect_k(inta[N],intlow,inthigh,intintq=intposq- k-1high-low returna[low]; returna[q];elseif(k<pos)returnSelect_k(a,low,q-1,k);return}

returnSelect_k(a,q+1,high,k- int{intlow,q,high,n,i,k,highes,a[N];for(i=0;i<n;i++)}return}在有序表中查找元素常常使用二分查找（BinarySearch），有时也译为“折半查找”。它midhigh8-7：逐步缩小范围法是一种常见的思维方法。二分查找便是基于这种思路，它8-5二分查找（迭代实现#include<stdio.h>#includeintA[]=intbsearch(int*A,intx,inty,intv)（迭代）intm;while(x<y){m=x+(y-x)/2;if(A[m]==v) returnm;elseif(A[m]>v) y=m;elsex=m+1;}return-}intmain(){inti;for(i=1;i<=11;i++)assert(bsearch(A,0,11,i)==i-1);return0;}8-6二分查找求下界intlower_bound(int*A,intx,inty,intv){intm;while(x<y){m=x+(y-x)/2; }return}x,x+1,x+2,…,y-1，还可能是候选区间却是闭区间[x,y]。A[mv全部往后移动一个位置）后序列仍然有序。upper_boundintupper_bound(int*A,intx,inty,intv){intm;while(x<y){m=x+(y-if(A[m]<=v)x=m+1;elsey=m;}return}vL=R，区间为空。 例8-4范围统计。 1：aLalower_boundaL=n，相当于把不存在的元素看作无穷大。bR=0，相当于把不存在的元素看作无穷大。#include#includealgorithm>//STLsort,lower_boundupper_boundusingnamespacestd;intv[10000];intmain(){intn,m,a,b;scanf("%d%d",&n,&m);for(inti0;ini++)scanf("%d",&v[i]);sort(v,v+n); for(inti=0;i<m;scanf("%d%d",&a,&b); printf("%d\n",upper_bound(v,v+n,b)-lower_bound(v,v+n,a));}}

3L能同时被两个或骨牌覆盖。如图8-3所示为L型骨牌（三格板）的4种旋转方式。① ② ③ ④8-3L方格，且任何2个L型骨牌不得。，，立求解了。当使用一个①号三格板（图中阴影）2、3、432、3、412残12残3412残①34 8-44×43（8-5312残12残②341212③④残4343残 8-54×4Board[][]来模拟棋盘，Board[1][1]是棋盘的左上角方格。titleL0。覆盖残缺棋盘所需要的三格板数目为：(size2-1)/3。将这8-58-6(b0，相同数字的为同一骨牌。残 2残2233021341154455 8-64×4#include<iostream>usingnamespacestd;constintN=11;intBoard[N][N];inttile=dcsizevoidChessBoard(inttr,inttc,intdr,intdc,int{if(size==intt=++tile,s=if(dr<tr+s&&dc<tc+s)ChessBoard(tr,tc,dr,dc,s); tLBoard[tr+s-1][tc+s-1]=ChessBoard(tr,tc,tr+s-1,tc+s-1,}if(dr<tr+s&&dc>=tc+s)ChessBoard(tr,tc+s,dr,dc,s);else{Board[tr+s-1][tc+s]=t;ChessBoard(tr,tc+s,tr+s-1,tc+s,s);}if(dr>=tr+s&&dc<tc+s)ChessBoard(tr+s,tc,dr,dc,s); Board[tr+s][tc+s-1]=ChessBoard(tr+s,tc,tr+s,tc+s-1,}if(dr>=tr+s&&dc>=tc+s)ChessBoard(tr+s,tc+s,dr,dc,s);else{Board[tr+s][tc+s]=t;ChessBoard(tr+s,tc+s,tr+s,tc+s,s);}}voidDisyBoard(intsize){for(inti=1;i<=size;++i){for(intj=1;j<=size;++j)printf("%2d",Board[i][j]);}}int{ChessBoard(1,1,2,1,4);return}nn-1i行第j列为第ij12345678278564323465872876543218-7k=3#include<iostream>usingnamespacestd;intvoidCreattable(intr1,intc1,intr2,intc2,intsize){inti,j; inthalfsize=size/2; for(j=0;j<size;j++)halfsizeif(i<halfsize&&(j>=halfsize&&j<size))if((i>=halfsize&&i<size)&&if((i>=halfsize&&i<size)&&(j>=halfsize&&j<size))}}intmain(){inti,j,k,n=1; cout<<"运动员"<<table[i][0]<<cout<<table[i][j]<<"";}return}8.3.3的鬼，向其发送质子流消灭它。质子流由巨人发射，沿直线行进，遇到鬼后。由于质子流交叉是很的所有质子流经过的线段不能有交点请设计一种给巨人和鬼配对的方法8-8(a)所示。8-8(b)所示。这个配对过程是递归的，好比棋盘覆盖中一样。不会找不到这样的配对区1。因此“从少到多”的过程中一定会有“一样多”的时候。abc（按复利x，a(1+x)-cbxa=2000，b=4，c=510intmain(){doublea,c,x=0,y=100;inti,b;scanf("%lf%d%lf",&a,&b,&c);while(y-x>1e-5){doublem=x+(y-x)/2;doublef=a;for(i=0;i<b;i++)f+=f*m/100.0-c;if(f<0)x=m;elsey=m;}printf("%.3lf%%\n",x);return0;}nm（每个正整数恰好属于一个序232543123|25|4S(1)、S(2)、S(36109。xP(x)计算，每次尽量往右划分即可。二分最小值xP(x)MO(logM)，P(xO(n)（从左到右扫描一次即可O(nlogM)。#include<iostream>#include<ctime>usingnamespacestd;#defineN10#defineINFintjuge(inta[],intmid,int{intintseg=0;int{if(sum>mid){}} return0;return}intvalue(inta[],intlow,inthigh,int {returnhigh+1;{int 半returnvalue(a,low,mid- return}}int{inta[N];for(intifor=0;ifor<N;ifor++)cout<<a[ifor]<<"";//intintm=3;intmin=INF,max=0;for(inti=0;i<N&&a[i]!='{}int return}8.4贪心niwiC#include<stdio.h>#defineN100intvoidSort(intw[],intt[],intn)wt[i]wiwintfor(i=1;i<=n;i++)w1w for(i=1;i<n;i++){ if(k!=j)wt//排序完成后，t[iiw（标}}}voidLoading(intx[],intw[],intc,intn){inti;Sort(w,t,n);//对数组wtw xfor(i=1;i<=n&&w[t[i]]<=c;i++)}}intinti,n,c;intwhile(scanf("%d%d",&n,&c)!=EOF)n,总重量{for(i=1;i<=n;i++)wfor(i=1;i<=n;i++){max+=w[i]*x[i];}}} 125 1612923845110217168180 1 选择物体的最大总重量为n个物体,第iwiviCC。由C，而且除了最后一个以外，所有的物体要么不拿，要么拿走全部。#include<stdio.h>#include<iostream>#defineMAXSIZE100#defineM15//背包的载荷能力usingnamespacestd;//算法，贪心算voidGREEDY(floatw[],floatx[],intsortResult[],int{floatc=M;inti=0;inttemp=0;for(i0;in;i++)x[i]=0;for(i=0;i<n;i++) for(intj=0;j<n;j++) tempj;//得到取物体的顺序}if(w[temp]>c) }x[temp]1;/cw[temp];//}if(in)//x[temp]=c/w[temp]; }voidsort(floatx[],intsortResult[],int{inti=0,j=0;intindex=0,k=0;for(i0;in;i++)/0sortResult[i]=0;for(i=0;i<n;i++) floattemp=0;index=for(j=0;j<n;j++) if((temp<x[j])&&(sortResult[j]==0)) temp=x[j];index=}}if(sortResult[index]==0)sortResult[index]=}for(i=0;i<n;i++) }voidgetData(floatp[],floatw[],int*n){inti=0;printf("pleaseinputthetotalcountofobject:");scanf("%d",n);printf("Pleaseinputarrayofp:\n");for(i=0;i<(*n);i++)scanf("%f",printf("Nowpleaseinputarrayofw:\n");for(i=0;i<(*n);i++)scanf("%f",&w[i]);}voidoutput(floatx[],int{intprintf("\n\nafterarithmeticdata:advisemethod\n");for(i=0;i<n;i++)printf("x[%d]\t",i);for(i=0;i<n;i++)printf("%2.3f\t",x[i]);}int{floatp[MAXSIZE],w[MAXSIZE],inti=0,n=intsortResult[MAXSIZE];getData(p,w,&n); for(i=0;i<