前言
我对编程能力的认知包括三块：
- 基础知识：数据库、操作系统、网络原理等；
- 编码能力：软件架构（MVVM、MVP）、设计模式、编程语言（C、JAVA、C++）等；
- 思考能力：分析需求、算法设计、数学基础等；
大学时代，身边很多计算机、软件、网络专业的人就对算法存在莫名的反感；
刚出校门那会觉得自己玩了三年多算法没用，面试大公司的后台开发，问的都是Linux、网络编程、项目经验等；
开始项目开发之后，用到的更多是设计模式、数据库、网络编程，每日都是频繁的业务代码实现；
写了几年业务代码，慢慢熟悉工作之后，决定再捡起算法和数学。
对于来求职的人，我负责的技术面试流程都会按照这三大块大致询问一遍。
大多数人对于算法设计和数学这一块基本都是空白。
算法学习
算法的学习最简单的方式就是多练习。找一个提供算法练习的网站，思考，编码，验证，最后再看看别人的思路。
这次题目来自于codeforces，IDE用的Xcode。
实践
看完题目大意，先思考，再看解析；觉得题目大意不清晰，点击题目链接看原文。
A
题目链接
题目大意：N（N为偶数）个数字a[i] (1 ≤ a[i] ≤ 100)，把数字平分 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个车，问：每个车放完后，棋盘还剩多少格子是所有车攻击范围外？
n and m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ min(100 000, n^2))
代码实现：
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的字符串，找到最短的区间，包含字符串出现过的所有字符，输出区间长度。
n (1 ≤ n ≤ 100 000)
代码实现：
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，上下车和车掉头的时间忽略不计；所有人只坐一次汽车； 问：最少需要多少时间才能完成这段路程？
(1 ≤ n ≤ 10 000, 1 ≤ l ≤ 10^9, 1 ≤ v1 < v2 ≤ 10^9, 1 ≤ k ≤ n)
代码实现：
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。
