A (1). 金塊問題 （遞歸，分治）

#include<bits/stdc++.h>
using namespace std;

int n;
int a[100001];

int F_mx(int l,int r){
	if(l==r)
		return a[l];
	if(r-l==1)
		return max(a[l],a[r]);
	int mid=(l+r)/2;
	int l_mx=F_mx(l,mid);//向左查找
	int r_mx=F_mx(mid+1,r);//向右查找
	return max(l_mx,r_mx);
}
int F_mi(int l,int r){
	if(l==r)
		return a[l];
	if(r-l==1)
		return min(a[l],a[r]);
	int mid=(l+r)/2;
	int l_mi=F_mi(l,mid);//向左查找
	int r_mi=F_mi(mid+1,r);//向右查找
	return min(l_mi,r_mi);
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	cout<<F_mx(1,n)<<" "<<F_mi(1,n);
	return 0;
}

B (2). 求先序遍歷（二叉樹的遞歸，分治）詳細(xì)可見： 傳送門?傳送門2

#include<bits/stdc++.h>
using namespace std;

string mid,post;

void Dfs(string mid,string post) {
	if(post.empty())
		return;
	char root=post[post.size()-1];
	post.erase(post.size()-1,1);
	int k=mid.find(root);
	string l_mid=mid.substr(0,k);
	string r_mid=mid.substr(k+1);
	string l_post=post.substr(0,k);
	string r_post=post.substr(k);
	cout<<root;
	Dfs(l_mid,l_post);
	Dfs(r_mid,r_post);
}

int main() {
	cin>>mid>>post;
	Dfs(mid,post);
	return 0;
}

C (3). 循環(huán)賽問題（遞歸，分治）詳細(xì)可見：傳送門

#include<bits/stdc++.h>
using namespace std;

int a[101][101];
int n;

void copy(int x,int y,int cx,int cy,int form) {//拷貝函數(shù)
	//x y 初始位置
	//cx cy 目標(biāo)位置
	//form 規(guī)模
	for(int i=0; i<form; i++)
		for(int j=0; j<form; j++)
			a[cx+i][cy+j]=a[x+i][y+j];
}
void part(int form,int x,int y) {//分割函數(shù)
	if(form==1)
		return;
	int t=form>>1;
	part(t,x,y);//先割后拷
	part(t,x,y+t);
	copy(x,y,x+t,y+t,t);
	copy(x,y+t,x+t,y,t);
}

int main() {
	cin>>n;
	for(int i=1; i<=n; i++)
		a[1][i]=i;
	part(n,1,1);
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++)
			printf("%5d",a[i][j]);
		cout<<"\n";
	}
	return 0;
}

D (4). 找禮物 （二分查找）詳細(xì)可見：傳送門

#include<bits/stdc++.h>
using namespace std;

int n,k;
double x,y;
struct node {
	char name[20];
	long long l;
} a[100001];
bool cmp(node a,node b) {
	return a.l<b.l;
}
int f_ind(int l,int r,int t) {
	int mid;
	while(l!=r) {
		mid=(l+r)/2;
		if(a[mid].l==t)
			l=mid+1;
		else
			r=mid;
	}
	return l;
}

int main() {
	cin>>n>>k;
	for(int i=1; i<=n; i++)
		cin>>a[i].name>>x>>y,a[i].l=10000*sqrt(x*x+y*y);
	sort(a+1,a+1+n,cmp);
	int top=1;
	while(--k) {
		top=f_ind(top,n,a[top].l);
		if(top==n)
			return printf("555...");
	}
	int t=a[top].l;
	int cnt=f_ind(top,n,t)-top;
	cout<<t/10000<<" "<<cnt<<"\n";
	for(int i=top; cnt; cnt--,i++) {
		cout<<a[i].name<<"\n";
	}
	return 0;
}

E (5). 排序工作量（歸并排序，逆序?qū)?，分治?/h3>

#include<bits/stdc++.h>
using namespace std;
int n,a[1000010],c[1000010];
long long ans;

void msort(int l,int r) { //歸并排序
	if(l==r)
		return;
	int mid=(l+r)/2,i=l,j=mid+1,k=l;
	msort(l,mid),msort(mid+1,r);
	while(i<=mid&&j<=r)
		if(a[i]<=a[j])
			c[k++]=a[i++];
		else {
			c[k++]=a[j++];
			ans+=mid-i+1;//統(tǒng)計(jì)答案
		}
	while(i<=mid)
		c[k++]=a[i++];
	while(j<=r)
		c[k++]=a[j++];
	for(int i=l; i<=r; i++)
		a[i]=c[i];
}

int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]),a[i]+=n-i;
	msort(1,n);
	printf("%lld",ans);
	return 0;
}

F (6). 基因編碼（遞歸，分治）

//定義0000這樣的序列為0序列 1111這樣的序列為1序列 0110這樣的為01序列

#include<bits/stdc++.h>
using namespace std;

string s,c;

char t(string s) {
	char ch=s[0];
	for(int i=1; i<s.size(); i++)
		if(s[i]!=ch)
			return 'C';//01序列為C
	return ch-'0'+'A';0序列回歸A 1序列回歸B
}
void f(string s) {
    //遞歸迭加字母
	c+=t(s);
	if(s.size()==1||t(s)!='C')
		return;//非01序列不在參與迭加如0100 會分成01和00 01會進(jìn)一步分從0和1而00應(yīng)該直接變成A
	f(s.substr(0,s.size()/2));
	f(s.substr(s.size()/2));
}

int main() {
	cin>>s;
	f(s);
	cout<<c;
	return 0;
}

H (8). 考分鄙視（歸并排序，逆序?qū)?，分治?/h3>

#include<bits/stdc++.h>
using namespace std;
int n,a[1000010],c[1000010];
long long ans;

void msort(int l,int r) { //歸并排序
	if(l==r)
		return;
	int mid=(l+r)/2,i=l,j=mid+1,k=l;
	msort(l,mid),msort(mid+1,r);
	while(i<=mid&&j<=r)
		if(a[i]<=a[j])
			c[k++]=a[i++];
		else {
			c[k++]=a[j++];
			ans+=mid-i+1;//統(tǒng)計(jì)答案
		}
	while(i<=mid)
		c[k++]=a[i++];
	while(j<=r)
		c[k++]=a[j++];
	for(int i=l; i<=r; i++)
		a[i]=c[i];
}

int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]),a[i]+=n-i;
	reverse(a+1,a+1+n);
	msort(1,n);
	printf("%lld",ans%12345);
	return 0;
}

I (9). 桐桐查單詞（二分查找）

#include<bits/stdc++.h>
using namespace std;

struct node {
	int page;
	char name[210];
} a[20001];
int n,m;
char s[210];

bool cmp(node a,node b) {
	return strcmp(a.name,b.name)<0;
}
int f_ind(int l,int r,char* t) {
	int mid;
	while(l!=r) {
		mid=l+r>>1;
		if(strcmp(a[mid].name,t)>0)
			r=mid;
		else if(strcmp(a[mid].name,t)<0)
			l=mid+1;
		else
			return mid;
	}
	return l;
}

int main() {
	cin>>n;
	for(int i=1; i<=n; i++)
		cin>>a[i].name>>a[i].page;
	sort(a+1,a+1+n,cmp);
	cin>>m;
	while(m--) {
		cin>>s;
		cout<<a[f_ind(1,n,s)].page<<"\n";
	}
}

J (10). 豬八戒吃西瓜（二分查找）

#include<bits/stdc++.h>
using namespace std;

int n,m,k;
int a[100001];

int f_ind(int l,int r,int t) {
	int mid;
	while(l!=r) {
		mid=l+r>>1;
		if(a[mid]>=t)
			r=mid;
		else
			l=mid+1;
	}
	return l;
}

int main() {
	cin>>n;
	for(int i=0; i<n; i++)
		cin>>a[i];
	sort(a,a+n);
	cin>>m;
	while(m--) {
		cin>>k;
		cout<<f_ind(0,n-1,k)+1<<"\n";
	}
}

K (11). 化妝晚會（二分查找）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;

int n,s,ans,cnt;
int a[N];

int Find(int l,int r,int t) {
	int mid;
	while(l!=r) {
		mid=l+r>>1;
		if(a[mid]<=t)
			l=mid+1;
		else
			r=mid;
	}
	return l;
}

int main() {
	cin>>n>>s;
	for(int i=0; i<n; i++)
		cin>>a[i];
	sort(a,a+n);
	while(a[cnt]<=s/2) {
		ans+=Find(cnt,n,s-a[cnt])-cnt-1;
		cnt++;
	}
	cout<<ans;
}

L (12). 珍珠項(xiàng)鏈 （二分查找）

#include<bits/stdc++.h>
using namespace std;

int a[100001];
int n,m,l,r;

int find_L(int l,int r,int t) {
	int mid;
	while(l!=r) {
		mid=l+r>>1;
		if(a[mid]>=t)
			r=mid;
		else
			l=mid+1;
	}
	return l;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n;
	for(int i=0; i<n; i++)
		cin>>a[i];
	sort(a,a+n);
	cin>>m;
	while(m--) {
		cin>>l>>r;
		if(l>r)
			swap(l,r);
		cout<<find_L(0,n,r+1)-find_L(0,n,l)<<"\n";
	}
	return 0;
}

M (13). 木材加工（二分答案）

#include<bits/stdc++.h>
using namespace std;

int n,k,l,r;
int a[100001];

bool judge(int l){
	int ans=0;
	for(int i=0;i<n;i++)
		ans+=a[i]/l;
	return ans>=k;
} //判斷當(dāng)木板長度為l時，能夠得到的木板數(shù)是否符合條件
int fin_D(int l,int r){
	int mid;
	while(l!=r){
		mid=l+r>>1;
		if(judge(mid))
			l=mid+1;//若可以符合，說明此時木板可能還不是最長，繼續(xù)向右逼近
		else                           //                             ^
			r=mid;//若不符合，則需要向左 //                    如上_   ^ ^ 
	}
	return l-1;//在向右逼近過程中，會得到答案，但是為了試探該答案是不是最優(yōu)解會向右+1試探一下
}

int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
		cin>>a[i],r+=a[i];
	if(k>r)//若總長不足以滿足k個木板長度為1
		return printf("0");
	cout<<fin_D(l,r);
}

N (14). 探險(xiǎn)（待補(bǔ)）

O (15). 奇怪的函數(shù)（二分答案）

#include<bits/stdc++.h>
using namespace std;
using ll=long long ;
const int N=2e9+5e8;

int n;

int main() {
	cin>>n;
	ll l=1,r=N,mid;
	while(l!=r) {
		mid=l+r>>1;
		ll t=trunc(log10(mid)/mid)+1;
		if(t<n)
			l=mid+1;
		else
			r=mid;
	}
	cout<<l;
}

文章來源地址http://www.zghlxwxcb.cn/news/detail-436480.html

到了這里，關(guān)于ACM實(shí)訓(xùn)-分治算法（二分，遞歸分治，歸并排序）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！