分治
分治的核心思想是
- 自上而下通过递归不断将大问题拆分成两个或多个子问题，直至被拆分出来的子问题可以通过一些简单的方法解决
- 然后再自下而上地用子问题的解求解大问题的解
- 最终我们能得到初始问题的解
解决分治问题的时候的代码基本就是
- 限制左边界 == 右边界的时候返回值
- 将区间一分为二，根据条件进行模拟
例题1 求逆序对
有 n 个数 a1,a2,…,an，对于其中的两个数字 x,y，如果满足 x 出现的位置在 y 出现的位置前面并且 x 比y 大，则称 (x,y)为数组 a 的一个逆序对。请问数组 a 的逆序对一共有多少个？形式化的说，请求出有多少组 (i,j) 满足 i<j 并且 ai>aj。
输入格式
第一行一个整数 n。接下来一行 nn 个整数，a1,a2,…,an。
输出格式
一行一个数，表示答案。样例输入
4
4 2 3 1
样例输出
5
样例解释
5 个逆序对分别为 (4,2),(4,3),(4,1),(2,1),(3,1)。数据范围
对于 100% 的数据，保证 2≤n≤100000,1≤ai≤n 并且每个数字都只会出现一次。
分治思路
我们可以思考一下如果将这个区间分为两半，那么逆序对的数量就是左区间逆序对数量加右区间逆序对数量加左边区间中去右边区间元素大的数量 ，这样我们就将原问题转化成了更小的子问题
代码
# include<bits/stdc++.h>
# define int unsigned long long
using namespace std;
int q[1000010];
int f(int q[],int l,int r)
{
if(l == r) return 0;
int mid = l+r >>1;
int x = 0;
vector<int> a,b;
for(int i=l;i<=mid;i++) a.push_back(q[i]);
for(int i=mid+1;i<=r;i++) b.push_back(q[i]);
sort(a.begin(),a.end());sort(b.begin(),b.end());
int len1 = a.size(),len2 = b.size();
for(int i=0,j = 0;i<len1 && j<len2;)
{
if(a[i]>b[j])
{
x+=(len1-i);
j++;
}
else if(a[i] <= b[j]) i++;
}
return f(q,l,mid)+f(q,mid+1,r)+x;
}
signed main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) scanf("%d",&q[i]);
cout<<f(q,0,n-1);
return 0;
}
例题2
给你一个长度为 n 的由小写字母组成的字符串 s，保证 n=2k 其中 k 为大于等于零的整数。
一个非空字符串 s 被称为 c-good（c 为 a...z 中的某个字母）的，需要满足下列三个条件之一：
s 长度为 1，且只含有 c 字符；
s 长度大于 1，且 s 的前一半全为字符 c，后一半为 next(c)-good 的字符串，其中 next(c) 表示 c 后面的那一个字母；
s 长度大于 1，且 s 的前一半为 next(c)-good 的字符串，后一半全为字符 c；
例如 aabc 是 a-good 的，ffgheeee 是 e-goodgood 的。对于给定的字符串 s，请求出最少改变 s 中几个字符可以把它变成 a-good 的字符串。
输入格式
输入有多组询问。第一行一个整数 TT 表示数据组数。
对于每组数据包含两行，第一行一个整数 n，第二行一个长度为 n 的字符串 s。
输出格式
对于每组数据，输出一行一个整数表示答案。样例输入
5
8
bbdcaaaa
8
asdfghjk
8
ceaaaabb
8
bbaaddcc
1
z
样例输出
0
7
4
5
1
数据规模
对于 100% 的数据，保证 1≤T≤5,1≤n≤131072，保证 n=2k，其中 𝑘 为大于等于零的整数。
我们可以将长度大于1的字符串的两种改变方案所需要的操作数都求出来取最小值就是答案。
代码
# include<bits/stdc++.h>
using namespace std;
string s;
int slove(int l,int r,char ch) //将字符串从l到r变成ch-good所需要的贡献
{
if(l == r)
{
if(s[l] == ch) return 0;
else return 1;
}
else
{
int mid = l+r >> 1;
int res1 = 0,res2 = 0;
for(int i=l;i<=mid;i++) if(s[i] != ch) res1++;
for(int i=mid+1;i<=r;i++) if(s[i] != ch) res2++;
return min ( slove(mid+1,r,ch+1)+res1,slove(l,mid,ch+1)+res2 );
}
}
int main()
{
int t;cin>>t;
while(t--)
{
int n;scanf("%d",&n);
cin>>s;
cout<<slove(0,n-1,'a')<<endl;
}
return 0;
}
例题3 : 平面最近点对
给定平面上 n 个点，你需要求出其中最近的一对点的欧几里得距离。
输入格式
第一行一个整数 n。接下来 n 行，每行两个数 xi,yi， 表示一个点的坐标。
输出格式
输出一行一个数表示答案，相对误差或绝对误差在 10−6 内即为正确。样例输入
3
1.0 2.0
1.0 3.0
1.0 5.0样例输出
1.00000000
数据规模
对于 100% 的数据，保证 1≤n≤2×105,0≤xi,yi≤109
我们将这些点集的x从小到大排序，每次分为两部分。最近距离就是左边集合中最近距离和右边集合中最近距离和一个点在左集合一个点在右集合的最短距离 这三者的最小值
我们先设左右两个最短距离的最小值为d ，对于一个点在左集合一个点在右集合中的点，我们将这个点到中间点的距离小于d的点加入一个集合c中，
将c的y从小到大排列，暴力枚举每个邻点并更新d，最后得到的d即为答案
代码
# include<bits/stdc++.h>
using namespace std;
typedef pair<double,double> pii;
const int N = 2e5+10;
pii a[N];
double solve(int l,int r)
{
if(l == r) return 0x3f3f3f3f;
int mid = (l+r)/2;
vector<pii> c;
double d = min(solve(l,mid),solve(mid+1,r));
for(int i=l;i<=r;i++)
if(abs(a[i].first-a[mid].first)<d)
c.push_back({a[i].second,a[i].first});
sort(c.begin(),c.end());
int len = c.size();
for(int i=0;i<len;i++)
for(int j=i+1;j<len && c[j].first>c[i].first<d;j++)
{
double y1 = c[i].first,x1 = c[i].second;
double y2 = c[j].first,x2 = c[j].second;
d = min(d,sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)));
}
return d;
}
int main()
{
int n;cin>>n;
for(int i=0;i<n;i++) cin>>a[i].first>>a[i].second;
sort(a,a+n);
printf("%.10f",solve(0,n-1));
return 0;
}