本文主要是介绍福州DAY6，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
转眼之间，5天就过去了。今天是第6天了，我们讲了分治和贪心两种思想。因为某种特殊的原因，今天就以分治为主讲吧（其实只是想博客写短一点，当然，最主要的目的是看起来方便、美观）。
分治：要想学习一种知识，首先要了解它的特点和作用。上面已经用粗体标注过了。首先要注意的是，分治其实是一种思想，并不是一种算法（by老师）。把分治二字拆开来说就是分而治之。详细的来说就是把一个原始的不能直接求的问题分成若干个比较好求的子问题，然后把它们合并起来，得到最后的解。
分治的使用对象和使用方法：分治使用的领域非常广，也是我们平时经常用到，普遍会在不知不觉中就接触的神奇的东西。今天最让我感到惊奇的是，在搜索题，竟然也可以用分治来解决。首先我觉得吧，要用分治的题目肯定要麻烦，一下子可能不能直接求出来，不然我们也就不会用分治了。在把原问题拆成子问题的时候，我们必须要满足原问题和子问题要是大致相同的，必须得是“一类”的问题，不然是进行不了分治的。所以，我们首先要做的就是把它们转成一类题。总的来说，分治的对象要好拆、好合，子问题好求。
讲了这么多的描述，那么就先来道经典的例题吧!
经典例题——逆序对
逆序对是一道非常经典的分治题，同时这一道题的解法也特别多。在之前的几天课中，我们已经学会了用树状数组来求逆序对，那么我们再来复习一下来凑字数吧。逆序对已经碰到多次了，这里就不讲题目描述了。这一次，我们用归并排序来求逆序对。
那么问题来了，为什么用归并排序就能够求逆序对对数了呢？其实我们可以不断地把一整个数列分成两半，对于后半部分中的每个数字，统计前半部分中比他大的数字的个数，这道题就可以完美的解决了。合并两个有序的序列用时O（n），如果序列长度为1不用排序，在通过递归，时间复杂度为O（nlogn）总体来说是非常高效的。
———————————————华丽丽的分割线———————————————
long long ans=0;
int a[100003],b[100003];inline void swap(int a,int b)
{int t;t=a;a=b;b=a;
}inline void gbsort(int l,int r)
{int mid,tmp,i,j;if(r>l+1){mid=(l+r)/2;gbsort(l,mid-1);gbsort(mid,r);tmp=l;for(int i=l,j=mid;i<=mid-1 && j<=r;){if(a[i]>a[j]){b[tmp++]=a[j++];cnt+=mid-i;}elseb[tmp++]=a[i++];}if(j<=r)for(;j<=r;j++) b[tmp++]=a[j];elsefor(;i<=mid-1;i++) b[tmp++]=a[i];for(i=l;i<=r;i++)a[i]=b[i];}else{if(l+1==r)if(a[l]>a[r]){swap(a[l],a[r]);cnt++;}}
}———————————————华丽丽的分割线———————————————
本来还想写二分查找和快速幂的，才发现以前原来就已经写过了，好像的确没有什么东西好讲的（实际上是我没有什么会讲），如果要看的话就去点击打开链接吧（溜了溜了
这篇关于福州DAY6的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
