NOIP基础算法——贪心和分治pascal.ppt

NOIP基础算法——贪心和分治pascal
LOGO
第五部分 分治策略
一、分治思想
分治(divide-and-conquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题的有序数列，每个数列中仅有一个数字；再将相邻的两列数据合并成一个有序数列；再重复上面的合并操作，直到合成一个有序数列。按照分治三步法来说，
归并过程为：
（1）划分：把序列分成元素个数相等的两半；
（2）递归求解：把两半分别排序；
（3）合并：把两个有序表合成一个有序表；
分析
显然，前两部分是很容易完成的，关键在于如何把两个有序表合成一个。每次只需要把两个序列中当前的最小元素加以比较，删除较小元素并加入合并后的新表。
核心参考代码
procedure MergeSort(left,right:integer)//归并排序
begin
if left=right then exit; //只有一个元素
mid:=(left+right)div 2; //找中间位
MergeSort(left,mid); //对左边归并
MergeSort(mid+1,right); //对右边归并
i:=left;j:=mid+1,p:=left; //合并左右
while(i<=mid and j<=right)do
if(a[i]>a[j])then begin temp[p]:=a[j];inc(p);inc(j);end
else begin temp[p]:=a[i];inc(p);inc(i);end
while(i<=mid)do begin temp[p]:=a[i];inc(p);inc(i);end
while(j<=right)do begin temp[p]:=a[j];inc(p);inc(i);end
for i:=left to right do a[i]:=temp[i];
End;
【变形1】逆序对数目
例题3：求“逆序对”。
给定一整数数组A=(A1,A2,…An), 若i<j且Ai>Aj,则<i,j>就为一个逆序对。例如数组（3，1，4，5，2）的逆序对有<3,1>,<3,2>,<4,2>,<5,2>。问题是，输入n和A数组，统计逆序对数目。
数据范围：1<=n<=30000。
朴素算法
在看完试题以后，我们不难想到一个非常简单的算法——穷举算法，即对数组中任意的两个元素进行判断，看它们是不是构成“逆序对”，因此这种算法的时间复杂度为O(N2)。
C:=0;
for i:=1 to n -1 do
for j:=i+1 to n do
if a[i]>a[j] then c:=c+1;
时间效率不尽如人意…..
问题出现在哪里呢？？
分治算法：
采用二分法求解:
记数列a[st,ed]的逆序对数目为d(st,ed);

mid=[(st+ed)/2],则有：
d(st,ed)=d(st,mid)+d(mid+1,ed)+F(st,mid,ed)
其中F(st,mid,ed)表示一个数取自a[st,mid],令一个数取自a[mid+1,ed]的逆序对数目。
和归并排序一样，划分和递归求解都好办，关键在于合并：如何求出i在左边，而j在右边的逆序对数目呢？统计的常见技巧是“分类”。我们按照j的不同把这些“跨越两边”的逆序对进行分类：只要对于右边的每个j，统计左边比它大的元素个数f(j)，则所有f(j)之和便是答案。
幸运的是，归并排序可以帮助我们“顺便”完成f(j)的计算：由于合并操作是从小到大进行排序的，当右边的a[j]复制到T中时，左边还没有来得及复制到T的那些数就是左边所有比a[j]大的数。此时累加器中加上左边元素个数mid-i+1即可。
即把“if(a[i]>a[j])then begin temp[p]:=a[j];inc(p);inc(j);end
改为“if(a[i]>a[j])then
begin tot:=tot+mid-i+1;temp[p]:=a[j];inc(p);inc(j);end
4、二分查找
【问题描述】给出从小到大排列的n个不同数a[1]~a[n]，试判断元素x是否出现在表中。