1、为什么要实战？
曾经有人问我，你写代码又快又好，是怎么学的呀？
其实我的水平也才一般般的啦，之所以能把程序写出来，只有多练习。
看别人的算法，很快就看完了，但往往看完就忘记了，只有自己亲自写一遍，调试运行一边，才能够掌握。
在练习几道题，举一反三，才算是掌握，才能够实际应用。
刚开始的时候，面对题目编程，大多数人都是心有余而力不足。
那些熟练的“码农”们，也只有非常努力，才能看起来毫不费力，最初的过程都是痛苦、缓慢的提升，慢慢走下去，才能成为合格的程序员！
亲自写一写
2、试题一《折叠绳子》
题目：
给定一段一段的绳子，你需要把它们串成一条绳。每次串连的时候，是把两段绳子对折，这样得到的绳子又被当成是另一段绳子，可以再次对折去跟另一段绳子串连。每次串连后，原来两段绳子的长度就会减半。
给定N段绳子的长度，绳子必须全部用上，你需要找出它们能串成的绳子的最大长度。
结绳
输入：每个测试用例第1行给出正整数N (2 <= N <= 10000)；第2行给出N个正整数，即原始绳段的长度，数字间以空格分隔。
输出：
在一行中输出能够串成的绳子的最大长度。结果向下取整，即取为不超过最大长度的最近整数。
在看解析之前，开动脑筋，应该怎么做呢？
解析：
最开始的绳子折叠的次数越多，所以应该先折叠短的绳子，之后折叠长的：
首先对绳子进行排序，之后按照要去折叠就可以了。
- 读入数据
- 排序
- 折叠
- 输出结果
参考代码：
/*
输入：
8
6 5 3 1 8 7 2 4
输出：
1 2 3 4 5 6 7 8
*/
#include <stdio.h>
using namespace std;
int a[100001];
//快速排序
void quicksort(int left, int right) {
int i, j, temp;
//终止条件
if (left>right)
return;
temp = a[(left + right) / 2];
i = left;
j = right;
//从左到右找到比基准数大的，从右到左找到比基准数小的，交换位置，直至两个过程相遇即全部比较完成
while (i != j) {
while (a[j] >= temp && i<j)
j--;
while (a[i] <= temp && i<j)
i++;
if (i < j) {
int l = a[i];
a[i] = a[j];
a[j] = l;
}
}
//将基准数的位置放在大小分割的中间
a[(left + right) / 2] = a[i];
a[i] = temp;
//左边递归过程
quicksort(left, i - 1);
//右边递归过程
quicksort(i + 1, right);
}
int main() {
int n, length = 0;
scanf("%d", &n);
//读入数据
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
//快速排序
quicksort(1, n);
//折叠，最开始将总长度设置为最短的一根，也就是a[1]，之后折叠
length = a[1];
for (int i = 2; i <= n; i++) {
length = (a[i] + length) / 2;
}
//输出结果
printf("%d ", length);
getchar(); getchar();
return 0;
}
3、试题二《判断主元》
《折叠绳子》的题目是不是很有趣？程序的思路跟上一节的快速排序基本一致，只是修改了main主程序里的几行代码。
下面，再写一道题练练手！
题目：
著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元（基准数），通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。
给定划分后的N个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？
例如给定N = 5, 排列是1、3、2、4、5，则：
1的左边没有元素，右边的元素都比它大，所以它可能是主元；
尽管3的左边元素都比它小，但是它右边的2它小，所以它不能是主元；
尽管2的右边元素都比它大，但其左边的3比它大，所以它不能是主元；
类似原因，4和5都可能是主元。
因此，有3个元素可能是主元。
输入：
输入在第1行中给出一个正整数N（<= 1000）； 第2行是空格分隔的N个不同的正整数，每个数不超过100000。
输出：
输出有可能是主元的元素个数。
在看解析之前，开动脑筋，应该怎么做呢？
解析：
对于每个数字，分别判断左边的数字是不是比它小，右边的数字是不是比它大，就可以了。
这种暴力求解的算法思路很清晰，但面对大量数据的情况下，运行时间就不容乐观，所以必须有更好的解决方案。
考虑到主元的性质，它左边的数字都比它小，它右边的都比它大，这跟排序完成的顺序是一样的！
输入顺序与排序
根据这个性质，可以快速求解。
- 读入数据，因为需要比较输入顺序和输出顺序，保存两份
- 排序
- 比较重复
- 输出结果
参考代码：
注意：为了节省篇幅， quicksort()函数没有写进去，自己运行过程中，需要补全。
void quicksort(int left, int right) {}
/*
输入：
5
1 3 2 4 5
输出：
3
*/
#include <stdio.h>
using namespace std;
int a[100000], b[100000], v[100000];
//快速排序
void quicksort(int left, int right) {}
int main() {
int n, max = 0, cnt = 0;
//读入数据
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
b[i] = a[i];
}
//排序
quicksort(1, n);
//比较输入顺序与排序后的顺序
for (int i = 0; i < n; i++) {
if (a[i] == b[i] && b[i] > max)
v[cnt++] = b[i];
if (b[i] > max)
max = b[i];
}
//输出结果
printf("%d\n", cnt);
getchar(); getchar();
return 0;
}
4、结尾
常见的排序方法基本讲完了，下一章将开启新的内容，是不是有些期待？
网友评论