程序员进阶之算法练习（一）
前言
我对编程能力的认知包括三块：
- 基础知识：数据库、操作系统、网络原理等；
- 编码能力：软件架构（MVVM、MVP）、设计模式、编程语言（C、JAVA、C++）等；
- 思考能力：分析需求、算法设计、数学基础等；
大学时代，身边很多计算机、软件、网络专业的人就对算法存在莫名的反感； 刚出校门那会觉得自己玩了三年多算法没用，面试大公司的后台开发，问的都是Linux、网络编程、项目经验等； 开始项目开发之后，用到的更多是设计模式、数据库、网络编程，每日都是频繁的业务代码实现； 写了几年业务代码，慢慢熟悉工作之后，决定再捡起算法和数学。
对于来求职的人，我负责的技术面试流程都会按照这三大块大致询问一遍。 大多数人对于算法设计和数学这一块基本都是空白。
算法学习
算法的学习最简单的方式就是多练习。找一个提供算法练习的网站，思考，编码，验证，最后再看看别人的思路。 这次题目来自于codeforces，IDE用的Xcode。
实践
看完题目大意，先思考，再看解析；觉得题目大意不清晰，点击题目链接看原文。
A
题目链接 题目大意：N（N为偶数）个数字，把数字平分 N/2 组，使得每组的数字和相等。 代码实现：
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
node[i].pos = i + 1;
cin >> node[i].value;
}
sort(node, node + n);
for (int i = 0; i < n / 2; ++i) {
cout << node[i].pos << " " << node[n - i - 1].pos << endl;
}题目解析：
假设最后的和为k，那么有k = sum / (N / 2); sum为所有数字之和。 对于数字a[i]，在数组中查找没有分配过的a[j] = k - a[i]即可。
优化：对n个数字的数组从小到大排序，对于a[0]（最小），它的另一个必然是a[n - 1]（最大）; 证明：假设a[0]对应的是a[n -2]，并且a[n -2] < a[n -1]，那么对于a[n -1]的数字和另外一个数字之和必然大于a[0]+a[n - 2]；
B
题目链接 题目大意：NxN的棋盘，每个格子可以放一个车，有M个车，问：每个车放完后，棋盘还剩多少格子是所有车攻击范围外？ 代码实现：
long long n, m, sum;
cin >> n >> m;
sum = n * n;
long long rowNum, colNum;
rowNum = colNum = 0;
while (m--) {
int x, y;
cin >> x >> y;
if (!row[x]) {
sum -= n - colNum;
}
if (!col[y]) {
sum -= n - rowNum;
}
if (!row[x] && !col[y]) {
++sum;
}
if (!row[x]) {
++rowNum;
row[x] = 1;
}
if (!col[y]) {
++colNum;
col[y] = 1;
}
cout << sum << " ";
}题目解析：
棋盘放下去一个车有横竖的影响，分开考虑。 对于横行，如果之前已经放过，没有影响；如果之前没有放过，那么看有多少列已经添加，得出影响到的cell为n - colNum; 对于纵列，如果之前已经放过，没有影响；如果之前没有放过，那么看有多少行已经添加，得出影响到的cell为n - rowNum; 如果行和列都没添加过，那么会有个重叠的计算，需要去除：sum = sum + 1;
C
题目链接 题目大意：N个字符串，找到最短的区间，包含所有字符串出现过的字符，输出区间长度。 代码实现：
int n, sum = 0;
cin >> n;
cin >> str;
for (int i = 0; i < n; ++i) {
if (!flag[str[i]]) {
flag[str[i]] = 1;
++sum;
}
}
int left = 0, k = 0;
int ret = n;
for (int i = 0; i < n; ++i) {
if (!c[str[i]]) {
++k;
}
++c[str[i]];
if (k == sum) { //[left, i]区间，存在答案
while (c[str[left]] > 1) {
--c[str[left]];
++left;
}
ret = min(ret, i - left + 1);
}
}
cout << ret << endl;题目解析：
假设[1, right] 包含了所有的字符，其中：[left, right]这个区间就包含了所有的字符，那么[1, left]可以舍弃；
D
题目链接 题目大意：n个人要走一段路，路的长度为l，人的速度为v1，租了一辆载客量为k的车，速度为v2，上下车和车掉头的时间忽略不计；所有人只坐一次汽车； 问：最少需要多少时间才能完成这段路程？ 代码实现：
long long n, v1, v2, l, k;
cin >> n >> l >> v1 >> v2 >> k;
long m = (n + k - 1) / k;
double tmp = (v2 - v1) * 1.0 / (v1 + v2);
double t2 = l /((m - 1) * 1.0 * v1 * (tmp + 1) + v2);
double tb = tmp * t2;
double ret = (m - 1) * tb + m * t2;
printf("%.7f", ret);题目解析：
要尽快的到达目的地，我们可以制定如下的策略： 1、车每次都要尽可能载更多的人； 2、车在开的同时人也走； 3、车开一段路后就让人下车，接着走，然后回去接新的人；
要让时间最少，则必须所有人到达终点时间的时间一致；
- 因为每个人只能坐一次车，那么每个人坐车的时间应该是一致的，假设其为T1；车子每次载客完之后还要回来，这个时间为T2；
- 把人分成m组（由n和k统计而得），除了最后一组人，车每次都要经历一次T1+T2，最后一次组是T2的时间；
- 每个人走路的路程=v1 * （T1 + T2) * (m - 1)； 每个人坐车的路程=v2 * t； v1 * （T1 + T2) * (m - 1) + v2 * t = l
- T1和T2受到速度v1和v2的影响 车子开出去的路程 v2 * T2; 人被接到之前走的路程 v1 * (T1 + T2); 车子返程的时间 v2* T2; v2 * T2 = v1 * (T1 + T2) + v2 * T2;
###总结
这次所有题目的代码在这里[CF701](https://github.com/loyinglin/Codeforces/tree/master/701)。