【题目描述】

有一实数序列A[1]、A[2] 、A[3] 、……A[n-1] 、A[n] (n<10000)，若i<j，并且A[i]>A[j]，则称A[i]与A[j]构成了一个逆序对，求数列A中逆序对的个数。

例如，5 2 4 6 2 3 2 6，可以组成的逆序对有

（5 2），（5 4），（5 2），（5 3），（5 2），

（4 2），（4 3），（4 2），

（6 2），（6 3），（6 2），

（3 2）

共：12个

【输入描述】

共两行，第一行有一个正整数n，第二行有n个整数。

【输出描述】

只有一行为逆序对个数。

【样例输入】

8  5 2 4 6 2 3 2 6

【样例输出】

12

【题目描述】

Prince对他在这片大陆上维护的秩序感到满意，于是决定启程离开艾泽拉斯。在他动身之前，Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代，平衡是个梦想。因为有很多奇异的物种拥有各种不稳定的能量，平衡瞬间即被打破。KB决定求助于你，帮助他完成这个梦想。

一串数列即表示一个世界的状态。

平衡是指这串数列以升序排列。而从一串无序数列到有序数列需要通过交换数列中的元素来实现。KB的能量只能交换相邻两个数字。他想知道他最少需要交换几次就能使数列有序。

【输入描述】

第一行为数列中数的个数n,第二行为n ≤ 10000个数。表示当前数列的状态。

【输出描述】

输出一个整数，表示最少需要交换几次能达到平衡状态。

【样例输入】

4  2 1 4 3

【样例输出】

2

【题目描述】

有2n个棋子（n≥4）排成一行，开始位置为白子全部在左边，黑子全部在右边，如下图为n=5的情形：○○○○○●●●●●

移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。

如n=5时，成为：○●○●○●○●○●

任务：编程打印出移动过程。

【输入描述】

输入n。

【输出描述】

移动过程。

【样例输入】

7

【样例输出】

step 0:ooooooo*******--  step 1:oooooo--******o*  step 2:oooooo******--o*  step 3:ooooo--*****o*o*  step 4:ooooo*****--o*o*  step 5:oooo--****o*o*o*  step 6:oooo****--o*o*o*  step 7:ooo--***o*o*o*o*  step 8:ooo*o**--*o*o*o*  step 9:o--*o**oo*o*o*o*  step10:o*o*o*--o*o*o*o*  step11:--o*o*o*o*o*o*o*

【题目描述】

设有N个选手进行循环比赛，其中N=2M，要求每名选手要与其他N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。

【输入描述】

输入：M。

【输出描述】

输出：表格形式的比赛安排表。一行各数据间用一个空格隔开。

【样例输入】

3

【样例输出】

1 2 3 4 5 6 7 8  2 1 4 3 6 5 8 7  3 4 1 2 7 8 5 6  4 3 2 1 8 7 6 5  5 6 7 8 1 2 3 4  6 5 8 7 2 1 4 3  7 8 5 6 3 4 1 2  8 7 6 5 4 3 2 1

1. 前言

   所谓分治算法就是指分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称为二分法。

   比如，我们玩过最简单的猜数游戏，一开始，对方先想一个1000以内的正整数，然后你给出一个数x。对方只要回答“比x大”或者“比x小”或者“猜中”。

   开始猜测是1到1000之间，你可以先猜500。运气好的一次猜中，如果比500大，显然结果不是1到500之间，那么下一次就猜501到1000。如果比500下，那么下次就猜1到499。只要每次都猜测区间的中间点，这样就可以把猜测区间缩小一半。这样不超过10次询问区间就可以缩小为1，答案就会猜中了，这就是二分的基本思想。

2. 基本思想及策略

   分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

    分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

     如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

分治法适用的情况

分治法所能解决的问题一般具有以下几个特征：

1) 该问题的规模缩小到一定的程度就可以容易地解决

2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3) 利用该问题分解出的子问题的解可以合并为该问题的解；

4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

应用

（1）二分搜索

 （11）一元三次方程求解

快速排序：

void qsort(int left, int right){  	int i=left; j =right;  	mid=a[left+right]/2;  	while(i<=j){  		while(a[i]<mid) i++;   		while(a[j>mid]) j--;  		if(i<=j){  			swap(a[i],a[j]);  			i++;  			j--;  		}  	}  	if(left<j) qsort(left,j);  	if(i<right) qsort(i,right);  }

一元三次方程求解：

描述

有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。

给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。

输入

一行，包含四个实数a，b，c，d，相邻两个数之间用单个空格隔开。

输出

一行，包含三个实数，为该方程的三个实根，按从小到大顺序排列，相邻两个数之间用单个空格隔开，精确到小数点后2位。

样例输入

1.0 -5.0 -4.0 20.0

样例输出

-2.00 2.00 5.00

【题目描述】

Kri 喜欢玩数字游戏。 一天，他在草稿纸上写下了t 对正整数(x,y) ，并对于每一对正整数计算出了z=x*y*gcd(x,y);可是调皮的 Zay 找到了 Kri 的草稿纸，并把每一组的 y都擦除了，还可能改动了一些 z。

现在 Kri 想请你帮忙还原每一组的 y，具体地，对于每一组中的 x和 z，你需要输出最小的正整数 y，使得 z=x*y*gcd(x,y)  。如果这样的 y不存在，也就是 Zay 一定改动了z ，那么请输出 -1。 注：gcd(x,y) 表示 x和 y的最大公约数，也就是最大的正整数 d，满足 既是x 的约数，又是 y的约数。

【输入描述】

第一行一个整数 t ，表示有 对正整数 x和z 。

 接下来 t 行，每行两个正整数 x和z ，含义见题目描述。

【输出描述】

对于每对数字输出一行，如果不存在满足条件的正整数y ，请输出-1 ，否则输出满足条件的最小正整 数 y。

【样例输入1】

1  10 240

【样例输出1】

12

【样例1解释】

x*y*gcd(x,y)=10*12*gcd(10,12)=240

【样例输入2】

3  5 30  4 8  11 11

【样例输出2】

6  -1  1

【数据范围】

对于20%的数据，t,x,z<=103。 

对于40%的数据，t<=103,  x<106,  z<=109。 

对于另30% 的数据，t<104 。 

对于另20% 的数据，x<106 。 

对于100%的数据，1<=t<=5*105, 1<=x<=109, 1<=z<=263 。

【题目描述】

智慧之王 Kri 统治着一座王国。 这天 Kri 决定举行一场比赛，来检验自己大臣的智慧。 比赛由 n道判断题组成，有 m位大臣参加。现在你已经知道了所有大臣的答题情况，但尚未拿到答 案，于是你决定先行预测。 具体来说，对于第 i道题，有 x个大臣选对， y个大臣选错（显然有x+y=m ），如果x>y，那 么你预测这题答案为对，否则为错。为了方便，我们保证 m是奇数。 在统计完成后，你拿到了答案，你想知道通过你的预测方式你最后有几道题预测正确。

【输入描述】

第一行两个正整数 n,m，保证m 是奇数。 接下来 m行，每行n 个整数，第i 行第j个整数 aij代表第 i位大臣对第 j道题的答案， 1表示他选 对， 0表示他选错。 接下来1 行 n个整数， 表示比赛答案， 第i 个数 bi若为 1表示第i 道题答案是对，若为 0表示答案是 错。

【输出描述】

输出一个整数，表示你最后有几题预测正确。

【样例输入1】

3 3  1 0 1  0 1 1  0 1 0  1 1 1

【样例输出1】

2

【样例1解释】

第一题 你预测答案为错（即0），实际答案为1，预测错误。 

第二题 你预测答案为对（即1），实际答案为1，预测正确。

第三题 你预测答案为对（即1），实际答案为1，预测正确。 所以预测正确的题数为2。

【样例2输入】

5 6  1 0 1 1 1 0  0 1 0 1 1 1  0 0 1 0 1 0  1 0 1 0 1 0  0 1 0 1 0 0  1 0 1 0 1 0

【样例2输出】

4

【数据范围】

对于20%的数据，n<=5，m=1 。 

对于50%的数据，n<=10，m<=10 。 

对于100%的数据， n<=1000 , m<=1000，m为奇数 。

【题目描述】

路飞在和他朋友们一块玩一个游戏。由于路飞的机智，这个游戏由路飞担任裁判。

首先，路飞会给他们一个人一个编号，并且每个人的编号都不相同。接下来的每一个回合，会给一个数，编号不超过它的最大编号

的人要报出自己的编号。如果没有人的编号比路飞给出的数要小，那么编号最小的人要报出自己的编号。每个人可以重复报号。

路飞会按照一个列表顺次报出每个回合的数，他的朋友们想知道每回合报出的编号应该是多少？

【输入描述】

输入数据共3行。

第一行有两个整数n,m( 1<=n<=105 , 1<=m<=105 )，分别表示参与游戏的路飞朋友的个数和游戏回合数。

第二行n个整数 ai (1<=ai<=108) ，表示朋友们每个人的编号。对于 0<=i<j<n， 都有 ai<aj，即他们的编号递增排列。

第三行m个整数 qi(1 <= qi <=108), 表示每回合路飞给的数字。

【输出描述】

 输出共一行m个整数，表示每回合报出的编号，每两个整数之间一个空格，最后一个数后面没有空格。

【样例输入】

5 5  1 5 10 15 20  3 6 12 18 24

【样例输出】

1 5 10 15 20