分治法，第一是对递归的运用一定要熟悉。像我个人来说不是很喜欢递归的写法，所以对分治法的理解只能停留在“借鉴经典代码来解决问题”，而不能“自创解决问题的代码”，在日后的编程中一定要重视递归的练习。
第二是要分割成的子问题除了规模比父问题小之外，除规格外其他性质一定要和父问题相同。如棋盘覆盖问题。将2k*2k的棋盘分割成4个2^k-1的子棋盘时，因题目要求棋盘有一个特殊方格，所以棋盘的特殊方格必定在4个子棋盘之一中，其余3个子棋盘中无特殊方格。所以可以用一个L型骨牌覆盖这3个较小棋盘的会合处。这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格。这样就巧妙的将子问题和父问题变成了相同问题。
第三是分治法时间复杂度的分析要熟练：
https://pintia.cn/problem-sets/1305138978396434432/problems/1305143530747195392
https://pintia.cn/problem-sets/1307667254822240256/problems/1307667473903321088
二分搜索
#include<bits/stdc++.h> using namespace std; double formula(double x){ double ans=pow(x,5)-15*pow(x,4)+85*pow(x,3)-225*pow(x,2)+274*x-121; return ans; } int main(){ double x; double left=1.5; double right=2.4; double mid; while(left<right){ mid=(left+right)/2; if(fabs(formula(mid))<0.0000001){ cout<<fixed<<setprecision(6)<<mid; return 0; } else if(formula(mid)>0){ left=mid; } else if(formula(mid)<0){ right=mid; } } return 0; }略
https://pintia.cn/problem-sets/1310066661857550336
将快排模版稍微修改一下(加一个find函数)
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 6000000; ll partition(ll a[], ll left, ll right) { ll x = left; ll i = left + 1; ll j = right; while (true) { while (i <= j && a[i] <= a[x]) i++; //注意边界条件 while (i <= j && a[j] > a[x]) j--; //注意边界条件 if (i > j) break; //注意边界条件 swap(a[i], a[j]); } swap(a[left], a[j]); return j; } void qSort(ll a[], ll left, ll right) { if (left >= right) return; ll mid = partition(a, left, right); qSort(a, left, mid - 1); //注意是mid-1不是mid qSort(a, mid + 1, right); //注意是mid+1不是mid } ll find(ll a[], ll left, ll right, ll k) { ll pos = partition(a, left, right); if (pos == k - 1) return a[k - 1]; if (pos > k - 1) find(a, left, pos - 1, k); else find(a, pos + 1, right, k); } ll a[maxn]; int main() { ll n, m, t; scanf("%lld", &t); while (t--) { scanf("%lld%lld", &n, &m); for (ll i = 0; i < n; i++) scanf("%lld", &a[i]); printf("%lld\n", find(a, 0, n - 1, m)); } return 0; }在 O ( n l o g n ) 内 求 出 所 有 逆 序 对 ， 显 然 不 能 直 接 暴 力 , 联 想 到 归 并 排 序 的 特 性 , 所 以 对 归 并 排 序 稍 加 修 改 即 可 在 O ( n l o g n ) 内 求 出 所 有 逆 序 对 在O(nlogn)内求出所有逆序对，显然不能直接暴力,联想到归并排序的特性,所以对归并排序稍加修改即可在O(nlogn)内求出所有逆序对 在O(nlogn)内求出所有逆序对，显然不能直接暴力,联想到归并排序的特性,所以对归并排序稍加修改即可在O(nlogn)内求出所有逆序对
#include <iostream> using namespace std; int a[100001],temp[100001],ans=0; //ans即为逆序对数目 void mergesort(int left,int right,int mid); void merge(int left,int right) { if(left==right) return ; int mid=(left+right)/2; merge(left,mid); merge(mid+1,right); mergesort(left,right,mid); } void mergesort(int left,int right,int mid){ int i=left,j=mid+1,k=left,flag1=0,flag2=0; while(i<=mid && j<=right) { if(a[i]<=a[j]) { temp[k]=a[i]; k++,i++; } else { temp[k] = a[j]; k++, j++; ans++; //题目规定降序是逆序，所以遇到降序就让ans++ } } while(i<=mid) { temp[k]=a[i]; k++,i++; ans++; //这些剩下的都是降序 } while(j<=right) { temp[k]=a[j]; k++,j++; } for(int q=left;q<=right;++q){ a[q]=temp[q]; } } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",&a[i]); } merge(1,n); // for(int i=1;i<=n;++i){ // printf("%d ",a[i]); // } cout<<ans; return 0; }Ps:将两处ans删掉就是归并排序模版
取 值 范 围 取 ( 0 , 最 大 派 的 体 积 ] , 然 后 利 用 二 分 搜 索 暴 力 搜 出 满 足 条 件 的 值 取值范围取(0,最大派的体积],然后利用二分搜索暴力搜出满足条件的值 取值范围取(0,最大派的体积],然后利用二分搜索暴力搜出满足条件的值
check函数原理：
mid越大，可以分出的派的数量就越小，所以更新right（右边界），减小下一次mid的值，如果num>=f+1，那说明分出的派的数量已经满足要求，所以这时候要找到更大的mid，更新left（左边界），让每个人分到的派的体积尽可能大（前提是分出的派的数量要满足要求）
#include <iostream> #include<cmath> using namespace std; const double PI=acos(-1.0); const int MAXN = 1e4+6; double a[MAXN] = {};//每个派的体积 int n,f; bool check(double x) { int num=0;//本次按x作为半径可以分配的数量 for (int i=0; i<n; i++) { num+=a[i]/x;//充分利用数据类型转换 if (num>=f+1) { return true; } } return false; } int main() { //读入数据 scanf("%d%d", &n, &f); double right = 0; double left = 0; for (int i=0; i<n; i++) { scanf("%lf", &a[i]); a[i] = PI*a[i]*a[i];//计算出每个派体积 right = max(right, a[i]);//更新右边界 } //二分查找 const double EPS = 1e-5; double mid; while (right-left>EPS) { mid = (left+right)/2; if (check(mid)) { //可以分 left=mid; } else { right=mid; } } printf("%.3lf\n", left); return 0; }