# ARTS
## Algorithm
### [1046 Shortest Distance (20 point(s))](https://pintia.cn/problem-sets/994805342720868352/problems/994805435700199424)
题目的主要意思就是计算圆圈内任意两点间的最短距离。题目虽然简单，不过给出的条件也是很有挑战性：`N (in [3,10^5])` 和 `M (≤10^4)`。如果按照常规的遍历计算的话，将会有 `10^9` 的计算量，要想在规定的时间 `200ms` 内完成，恐怕不太现实。
这里可以换一个思路进行求解。我们可以计算出`每个点`到`第一个点`的距离，最后相减即可得到两点间的某方向的距离，两点间最短的距离也就出来了。不过需要提前缓存`每个点`到`第一个点`的距离。
```c
#include
#include
int calculateShortest(int *distancesToFirst, int total, int totalDistance, int left, int right) {
int leftToRightSum = *(distancesToFirst + left) - *(distancesToFirst + right);
if(leftToRightSum < 0) {
leftToRightSum *= -1;
}
int rightToLeftSum = totalDistance - leftToRightSum;
return leftToRightSum < rightToLeftSum ? leftToRightSum : rightToLeftSum;
}
int main() {
// Input N
int N = 0;
scanf("%d", &N);
// Initialize distances array dynamically
int *distancesToFirst = malloc((N + 1) * sizeof(*distancesToFirst));
int totalDistance = 0;
*distancesToFirst = 0;
// Input distances
for(int i = 0; i < N; i++) {
int exit = 0;
scanf("%d", &exit);
totalDistance += exit;
*(distancesToFirst + i + 1) = totalDistance;
}
// Input M
int M = 0;
scanf("%d", &M);
// Input a pair of exit number
for(int i = 0; i < M; i++) {
int left = 0;
int right = 0;
scanf("%d %d", &left, &right);
// Calculate the result and print
int shortestDistance = calculateShortest(distancesToFirst, N, totalDistance, left - 1, right - 1);
printf("%d\n", shortestDistance);
}
free(distancesToFirst);
return 0;
}
```
## Review
### Programs Are Translated by Other Programs into Different Forms (Section 1.2)
> Computer Systems: A Programmer's Perspective, Third Edition
具体讲解了源程序 `hello.c` 是如何被翻译为其他形式的程序的。这里由 `gcc` 为例。
- 预处理阶段 (Preprocessing phase)
预处理器将会修改 `hello.c` 部分内容并保存在 `hello.i`。比如 `#include` 这行代码，预处理器将会根据指令去寻找 `stdlib.h` 系统头文件，最后将相应的内容添加到 `hello.i`。注意，整个过程源码 `hello.c` 是不会变动的，且最终的 `hello.i` 也是文本文件。
- 编译阶段 (Compilation phase)
编译器将会将文本文件 `hello.i` 编译成为汇编代码，最后生成 `hello.s` 文本文件，类似下面这种类型：
```assembly
main:
subq $8, %rsp
movl ...
...
```
这里编译的汇编代码实际上是很有用的，因为它可以多种编译器提供统一的输出语言。
- 汇编阶段 (Assembly phase)
汇编器将会把上一步生成的文本文件 `hello.s` 进一步转换为`机器语言指令`，最后打包成为可重定位的对象文件 `hello.o`。如果用编辑器打开这个文件会发现，全是乱码。
- 链接阶段 (Linking phase)
终于到了最后的链接阶段了。这里以 `printf` 函数为例，`hello.c` 中调用了 `printf` 方法，链接器将会将预编译好的 `printf.o` 合并到 `hello.o` 中，最后形成 `hello` 这个可执行文件。
以上为一个简单 C 语言程序的翻译过程。
## Tip
### 分页插件
自制分页插件。虽然网上有大量现成的分页插件，但是依赖始终是不可控，导致最后的打包体积过于肥大。正好自己用 [vue](https://github.com/picturepan2/spectre) 来造一个简单而优雅的轮子。
这里所用的样式为 [Spectre](https://github.com/picturepan2/spectre)（轻量级，响应式，且现代的 `CSS` 库）。当然了，自己也可以写一个好看的样式出来，最后的体积将会更加小巧！
```javascript
```
## Share
在 Ubuntu 18.04 上建立 WireGuard 隧道组建 VPS 大内网
>
ARTS-w002