第八章 高效算法设计

第八章 高效算法设计

分治法求最大连续和

注意范围是[x,y)

#includeusing namespace std;int maxsum(int *A,int x,int y){ if(y-x==1) return A[x]; int m=x+(y-x)/2; int maxs = max(maxsum(A,x,m),maxsum(A,m,y)); int v,L,R; v=0; L=A[m-1]; for(int i=m-1;i>=x;i--) L=max(L,v+=A[i]); v=0; R=A[m]; for(int i=m;i

归并排序，注意范围还是[x,y)

归并就是先分治排序最小范围的序列

然后归并，归并紫书上有个图，思路很清晰

#includeusing namespace std;void merge_sort(int *A,int x,int y,int *T){ if(y-x>1){ int m=x+(y-x)/2; int p=x,q=m,i=x; merge_sort(A,x,m,T); merge_sort(A,m,y,T); while(p=y||(p

逆序对问题

同样的分治归并法，利用归并排序从m往前扫的特点，去数逆序对数

因为序列会排上序，所以直接加（m-p）即可

#includeusing namespace std;int cnt=0;void merge_sort(int *A,int x,int y,int *T){ if(y-x>1){ int m=x+(y-x)/2; int p=x,q=m,i=x; merge_sort(A,x,m,T); merge_sort(A,m,y,T); while(p=y||(p

快速排序：

从起始点选定一个点，从后往前扫，再从前往后扫

再选第二个点，知道选到最后

#includeusing namespace std;void quickSort(int a[],int left,int right){ int i=left; int j=right; int temp=a[left]; if(left >= right) return ; while(i!=j){ while(i=temp) j--; if(j>i) a[i]=a[j]; while(i

快速选择问题

根据快速排序划分后的标记点，判断序列要找的k是否大于或者小于它，然后进行方向性的枚举

#includeusing namespace std;int k=2;int quickSort(int a[],int left,int right){ int i=left; int j=right; int temp=a[left]; printf("temp:%d ** \n",a[left]); if(left >= right) return 0; while(i!=j){ while(i=temp) j--; if(j>i) a[i]=a[j]; while(ii) quickSort(a,i+1,right); else return a[k];}int main(){ int A[]={0,2,1,-1,-3}; // -3 -1 0 1 2 int T[100]; k=0; printf("%d\n",quickSort(A,0,4)); return 0;}

二分查找折半查找

迭代实现

#includeusing namespace std;int bsearch(int *A,int x,int y,int v){ int m; while(xv) y=m; else x=m+1; } return -1;}int main(){ int A[]={0,2,1,-1,-3}; // -3 -1 0 1 2 int T[100]; sort(A,A+5); printf("%d\n",bsearch(A,0,5,-3)); return 0;}

二分查找求上下界

STL中也有这两个函数可以直接用

#includeusing namespace std;int lower_bound(int *A,int x,int y,int v){ int m; while(x=v) y=m; else x=m+1; } return x;}int upper_bound(int *A,int x,int y,int v){ int m; while(x

棋牌覆盖问题

递归分治解决，边界为k==1

#includeusing namespace std;int cnt=0;int merge_qipan(int k){ if(k==1) return ++cnt; merge_qipan(k-1); merge_qipan(k-1); merge_qipan(k-1); merge_qipan(k-1); return ++cnt;}int main(){ int k; scanf("%d",&k); printf("%d\n",merge_qipan(k)); return 0;}

循环日程表问题：出不来

巨人与鬼：暂时忽略

贪心法：

最优装载问题：纯贪心

部分背包问题：按比值贪心

区间相关问题：选择不相交区间，按b排序

第一种：a1>a2 选择a1 然后：a1

区间选点问题：按b排序，第一个区间取最后一个点

区间覆盖问题：

预处理：

先切掉[s,t]外的部分

按a排序，起点非s，无解

否则选择起点为s的最长区间

然后新的起点为上一个区间的终点

Huffman编码:

先排序把字符排成表p，创建新节点队列，每次两两合并

构造法：

例题8-1：UVA120煎饼

书上给的分析很明白，其实就是让去找一个可行解，但不知道是不是最优

这种就叫构造算法吧，每次拍一次最大的，最大的排号就不用管了

问题是用数组实现起来真的很麻烦，看到一个666的题解，双端队列，还有reverse翻转，注意翻转是有顺序的。

#includeusing namespace std;int main(){ for(string strLine;getline(cin,strLine);cout<<'0'< Stack; for(int nDiam;iss>>nDiam;Stack.push_front(nDiam)) ; for(deque::iterator i=Stack.begin();i!=Stack.end();i++){ deque::iterator iMax = max_element(i,Stack.end()); if(iMax != i) { if(iMax != Stack.end()-1){ reverse(iMax,Stack.end()); cout<

例题8-2联合国大厦UVa1605

也是按紫书给的思路，共两层，第一层跟i一样放国家，下一层按列，这样每个第一层的国家会和第二层而且是每一个国家都挨着

注意国家只能用大小写字母

#includeusing namespace std;int a[60][60];int b[60][60];int main(){ int n; while(~scanf("%d",&n)){ printf("%d %d %d\n",2,n,n); for(int i=0;i25) printf("%c",a[i][j]-26+'a'); else printf("%c",a[i][j]+'A'); } printf("\n"); } printf("\n"); for(int i=0;i25) printf("%c",b[i][j]-26+'a'); else printf("%c",b[i][j]+'A'); } printf("\n"); } printf("\n"); } return 0;}

中途相遇法：从两个方向解决问题，最后汇总

8-3 UVa1152 和为0的四个值

这个题的Hash写的很精妙，好好体会

#includeusing namespace std;struct HashMAP{ static const int mask = 0x7fffff; int p[8388608],q[8388608]; void Clear() { for(int i=0;i<=mask; ++ i) q[i]=0; } int & operator [] (int k){ int i; for(i=k&mask; q[i]&&p[i]!=k;i=(i+1)&mask) ; p[i]=k; return q[i]; }}Hash;int main(){ int t; scanf("%d",&t); while(t--){ Hash.Clear(); int n,sum=0,a[4100],b[4100],c[4100],d[4100]; scanf("%d",&n); for(int i=0;i

问题分解：

例题8-4 传说中的车 UVa11134

和前面讲的区间相关问题类似，首先把图分为两个一维轴，然后根据给定的区间，按b排序，从前面找i的位置，找到便正确

#includeusing namespace std;struct pp { int x1,x2,y1,y2,x,y,num;}B[5050];bool cmp1(pp a,pp b) { if(a.x2==b.x2) return a.x1=i &&!B[j].x) { B[j].x=i; AA++; break; } } sort(B,B+n,cmp2);// for(int i=0;i=i &&!B[j].y) { B[j].y=i; BB++; break; } } if(AA==n&&BB==n){ sort(B,B+n,cmp3); for(int i=0;i

等价转换

例题8-5 UVa11054酒的交易

等价转换就是每一次都只考虑a2家酒庄需要多少劳力给a1家酒庄送酒，结果便是最优

#includeusing namespace std;int main(){ int n;while(cin>>n&&n){ int ans=0,a,last=0; for(int i=0;i>a;ans+=abs(last);last+=a; } cout<

扫描法：扫面法再枚举时维护一些重要的量，简化计算

例题8-6 两性亲子 UVa1606

极角排序的这个题并不会

#includeusing namespace std;struct Node{public : int x,y,z; double rad; bool operator < (const Node& rhs) const { return rad < rhs.rad; }}c[1000],d[1000];bool Turn(Node&a,Node&b){ return a.x*b.y>=a.y*b.x;}int main(){ int N; while(~scanf("%d",&N)&&N){ for(int i=0;i

窗口滑动法

例题8-7 唯一的雪花 UVa11572

其实就是一个循环便利，只不过根据题意如果遇到与当前序列重复的数，就需要从前面找到这个重复的数然后删掉

每次都记录最大的序列长度，便利一遍，即得结果，下面两个实现，一个set，一个map

#includeusing namespace std;const int maxn = 1e6 + 5;int B[maxn];int main(){ int t,N; scanf("%d",&t); while(t--){ scanf("%d",&N); for(int i=0;i s; int L=0,R=0,ans=0; while(R

用map算出上一次相同数的位置last数组

#includeusing namespace std;const int maxn = 1e6 + 5;int A[maxn],last[maxn];map cur;int main(){ int t,n; scanf("%d",&t); while(t--){ scanf("%d",&n); cur.clear(); for(int i=0;i

使用数据结构：

再不用改变主算法的情况下，提高运行效率

求f（i）i到k的最小值，要求f(1)...f(n-k+1)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。