二分及排序CopyRight

by

CDD2017年11月28日二分查找【例6

.

10】找數(shù)。給一個長度為n的單調(diào)增的正整數(shù)序列，即序列中

每一個數(shù)都比前一個數(shù)大。有m個詢問，每次詢問一個x,問序列中最后

一個小于等于x的數(shù)是什么?輸入格式：第1行，兩個整數(shù)n,m;接下來一行n

個數(shù)，表示這個序列；接下來m行每行一個數(shù)，表示一個詢問。輸出格式：輸出共m

行，表示序列中最后一個小于等于x

的數(shù)是什么。

寫如沒有，則輸出-1。輸入樣例：5312346513輸出樣例：413二分查找分析：我們用Left

表示詢問區(qū)間的左邊界，用Right

表示詢問區(qū)間的右邊界，[Left,Right]組成詢問區(qū)間。

一開始

Left=1,Right=n,序列已經(jīng)按照升序排好，保證了二分的有序性。每一次二分，我們這樣來做：(1)取區(qū)間中間值Mid=(Left+Right)/2。(

2

)

判

斷a[Mid]

與x的關(guān)系，如果a[Mid]>x,由于序列是升序排列，所以區(qū)間[Mid,Right]都可以被排除，修改右邊界Right=Mid-1。(

3

)

如

果a[Mid]<=x,修改左邊界Left=Mid+1

。

重復(fù)執(zhí)行二分操作直到Left>Right。下面我們來分析答案的情況，循環(huán)結(jié)束示意圖如圖6.19所示。圖6.19

二分循環(huán)結(jié)束示意圖最終循環(huán)結(jié)束時一定是Left=Right+1,根據(jù)二分第(2)步的做法我們

知道

Right

的右邊一定都是大于x

的，而根據(jù)第(3)步我們可以知道Left

左

邊一定是小于等于x的

。所以，

一

目了然，最終答案是Right

指向的數(shù)。Right=0就是題自中

輸出-1的情況。//eg6.10#include<iostream>using

namespace

std;int

n,m,a[110000];int

main(){cin

>>n

>>m;for(inti=1;i<=n;i++)cin>>a[i];a[0]=-1;for(inti=1;i<=m;i++){int

X;intleft=1,right=n,mid;cin>>X;while(left<=right){mid=(left+right)/2;if(a[mid]<=X)left

=mid

+1;

else

right

=mid

-1;}cout<<a[right]<<endl;}return

0;}123456789101112131415161718192021222324程序eg6.10

如下：二分查找【例

6

.11】月度開銷。農(nóng)夫約翰是一個精明的會計師。

他意識到

自己可能沒有足夠的錢來維持農(nóng)場的運轉(zhuǎn)了。他計算出并記錄下了接

下來

N(1≤N≤100,000)

天里每天需要的開銷。約翰打算為連續(xù)的

M(1≤M≤N)個財政周期創(chuàng)建預(yù)算案，他把一個財政周期命名為fajo

月。

每個fajo

月包含一天或連續(xù)的多天，每天被恰好包含在一個fajo

月里。約

翰的目標(biāo)是合理安排每個fajo

月包含的天數(shù)，使得開銷最多的fajo月的開

銷盡可能少。輸人格式：第1行，包含兩個整數(shù)N,M,用單個空格隔開；接下來N行，

每行包含一個1到10000之間的整數(shù)，按順序給出接下來N天里每天的開銷。輸出格式：

一個整數(shù)，即最大月度開銷的最小值。輸入樣例

：75100400300100500101400輸出樣例：500二分查找分析：不妨設(shè)ok(i)表示是否存在一種方案使得開銷最多的fajo

月的開銷小于等于i

。判斷ok(i)可以用貪心法，從左到右掃描每一天的開銷，

采用“物盡其用”原則，在不超過i

的前提下讓每一個fajo

月的天數(shù)越多越好，如果最終得到的預(yù)算案小于等于M,則ok(i)=1,答案可以比i再小一些，如果大于M,則ok(i)=0,答案要比i大一些。這就滿足了二分的有

序

性

。用L

表示二分區(qū)間左邊界，R

表示右邊界，當(dāng)L<=R時：(1)Mid=(L+R)/2。(2)如果ok(Mid)=1,則R=Mid-1,

否則L=Mid+1。重復(fù)執(zhí)行直到L>R,由

于L的左邊都是小于答案的，R的右邊是大于

等于答案的。所以最終答案就是L。程序如下：1//eg

6.112

#include

<iostream>3using

namespacestd;4constintMAXN=100005;5int

A[MAXN],N,M;6

boolok(intlimit)//判斷l(xiāng)imit對應(yīng)的fajo月數(shù)是否不超過M7

{8intc=1;9

for(int

i=1,sum

=0;i<=N;i

++)10

if(sum

+A[i]<=limit)sum+=A[i];else11

{12

++C;13

sum

=A[i];14

if(sum>limit)return0;15

}16

return

c

<=M;17

}18

int

main()19

{20

cin

>>N

>>M;21

for(int

i=1;i<=N;i

++)cin

>>A[i];22

int

1=1,r=10000

*N;23

while(1<=r)24

{25

int

mid=1+r>>1;26

if(ok(mid))r=mid

-1;else1=mid+1;27

}28

cout<<1<<endl;29

return

0;30

}快速排序【例6

.

12】排序。給你一個長度為n的序列，讓你給這個序列從小到

大排序。(n<=100000)輸入格式：第1行，一個整數(shù)n;第2行n個整數(shù)，表示這個序列。輸出格式：1行，

n

個整數(shù)，表示排序好的序列。輸入樣例：6245137輸出樣例：123457分析：

如果使用選擇排序，時間復(fù)雜度為O(n2)

。對于本題來說不能在1秒內(nèi)出解，超時。下面介紹快速排序?？焖倥判蚩焖倥判虻幕舅枷胧牵和ㄟ^一趟排序?qū)⒋庞涗浄指畛瑟毩⒌淖笥覂刹糠?，其中左邊的所有元素都比右邊的元素要小，接下來分別對這兩部

分繼續(xù)進(jìn)行排序，那么整個序列就有序了。當(dāng)i<=j

時

，i從當(dāng)前位置往右掃描找到第一個大于等于基準(zhǔn)數(shù)的元素.j

從當(dāng)前位置往左掃描找到第一個小于等于基準(zhǔn)數(shù)的元素，如果i<=j,交換a[i]與

a[j],交換完后a[i]小于等于基準(zhǔn)數(shù)，指針i

向右移動

一位，a[i

大于等于基準(zhǔn)數(shù)，指針j向左移動一位。重復(fù)執(zhí)行以上操作直到i>j為止。以上劃分把原序列劃分成三部分：(1)左邊{A[L],A[L+1],…,A[j]}:這一部分的元素小于等于基準(zhǔn)數(shù)T(2)中間{A[j+1],A[j+2],…,A[i-1]}:這一部分的元素等于基準(zhǔn)數(shù)T(3)右邊{A[i],A[i+1],…,A[R]}:這一部分的元素大于等于基準(zhǔn)數(shù)T

接下來對左邊和右邊進(jìn)行遞歸處理即可?？焖倥判?4)基準(zhǔn)數(shù)不能選擇第一個或者中間的位置固定的數(shù)，這樣的程序

有把程序卡得很慢的針對性的數(shù)據(jù)，建議用上面程序中隨機產(chǎn)生基準(zhǔn)數(shù)：

較

好

。第一遍84838887615070608099//將當(dāng)前序列在中間位置的數(shù)定義為分隔數(shù)//在左半部分尋找比中間數(shù)大的數(shù)//在右半部分尋找比中間數(shù)小的數(shù)//若找到一組與排序目標(biāo)不一致的數(shù)對則交換它們//繼續(xù)找//注意這里不能有等號//若未到兩個數(shù)的邊界，

則遞歸搜索左右區(qū)間int

i,j,mid,p;i=l;

j=r;mid=a[(l+r)/2];dowhile

(a[i]<mid)i++;while

(a[j]>mid)j--

;if(i<=j)p=a[i];if(i<r)

qso

rt(i,r);基準(zhǔn)只是一個比較數(shù)字，可以隨機使用，它在排序中也共同參與排序，沒有特殊

化。參考程序代碼1

快速排序算法2

void

qsort(int

l,int

r)a[i]=a[j];a[j]=p;i++;

j--;4程序eg6.12如下：1

//eg

6.122#include

<iostream>3#include

<algorithm>4#include

<ctime>5#include

<cstdlib>6

using

nanespace

std;7const

int

MAXN

=100005;8int

A[MAXN],N;9void

qsort(int

L,int

R)10

{11

if(L>=R)return;12int

i=L,j=R,T=A[rand()%(R-L+1)+L];13while(i<=j)14{15

while(A[i]<T)i++;16

while(A[j]>T)j--;17

if(i<=j)18{19

swap(A[i],A[j]);20

i++;21

j--;22

}23

}24

qsort(L,j);25qsort(i,R);

26}27

int

main()28{29

cin>>N;30for(inti=1;i<=N;i++)cin>>A[i];31srand(int(time(0)));32

qsort(1,N);33

for(inti=1;i<=N;i++)cout<<A[i]<<”“;34

cout<<endl;35return

0;36

}//快速排序合

并418

32834610

2578234567810合并過程為：比較a[i]和a[j]的大小，若a[i]≤a[j],

則將第一個有序表中的元素

a[i]復(fù)制到r[k]中，并令i和k分別加上1;否則將第二個有序表中的元素a[j]復(fù)制到r[k]

中，并令j和k分別加上1,如此循環(huán)下去，直到其中一個有序表取完，然后再將另一個有

序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)t的單元。歸并排序的算法我們通常用遞歸實

現(xiàn)，先把待排序區(qū)間[s,t]以中點二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]。歸并排序歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法(Divide

and

Conquer)的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序

的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序

表，稱為二路歸并。例如有8個數(shù)據(jù)需要排序：104638257歸并排序主要分兩大步：分解、合并。10463825

7104638257104828分

解歸并排序動態(tài)圖示6

5

3

1

8

7

2

4【程序?qū)崿F(xiàn)】void

msort(int

s,int

t){if(s==t)return;//如果只有一個數(shù)字則返回，無須排序int

mid=(s+t)/2;msort(s,mid);

//分解左序列msort(mid+1,t);

//分解右序列int

i=s,j=mid+1,k=s;

//

接下來合并while(i<=mid&&j<=t){if(a[i]<=a[j]){r[k]=a[i];k++;i++;}else{r[k]=a[j];k++;j++; while(i<=mid)