ARTS
Algorithm
1046 Shortest Distance (20 point(s))
题目的主要意思就是计算圆圈内任意两点间的最短距离。题目虽然简单，不过给出的条件也是很有挑战性：N (in [3,10^5]) 和 M (≤10^4)。如果按照常规的遍历计算的话，将会有 10^9 的计算量，要想在规定的时间 200ms 内完成，恐怕不太现实。
这里可以换一个思路进行求解。我们可以计算出每个点到第一个点的距离，最后相减即可得到两点间的某方向的距离，两点间最短的距离也就出来了。不过需要提前缓存每个点到第一个点的距离。
#include <stdio.h>
#include <stdlib.h>
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> 这行代码，预处理器将会根据指令去寻找 stdlib.h 系统头文件，最后将相应的内容添加到 hello.i。注意，整个过程源码 hello.c 是不会变动的，且最终的 hello.i 也是文本文件。
- 编译阶段 (Compilation phase)
编译器将会将文本文件 hello.i 编译成为汇编代码，最后生成 hello.s 文本文件，类似下面这种类型：
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 来造一个简单而优雅的轮子。
这里所用的样式为 Spectre（轻量级，响应式，且现代的 CSS 库）。当然了，自己也可以写一个好看的样式出来，最后的体积将会更加小巧！
<template>
<div>
<ul class="pagination">
<li class="page-item" :class="{ disabled: !hasPrev }">
<a tabindex="-1" href="javascript:void(0)" @click="handlePrevClick"
>Previous</a
>
</li>
<!-- Show first page -->
<li
class="page-item"
v-if="firstPage != null"
:class="{ active: page === firstPage }"
>
<a href="javascript:void(0)" @click="handlePageItemClick(firstPage)"
>{{ firstPage + 1 }}</a
>
</li>
<!-- Show middle page -->
<li class="page-item" v-show="hasMorePrev">
<span>...</span>
</li>
<li
class="page-item"
v-for="middlePage in middlePages"
:key="middlePage"
:class="{ active: middlePage === page }"
>
<a href="javascript:void(0)" @click="handlePageItemClick(middlePage)">
{{ middlePage + 1 }}
</a>
</li>
<li class="page-item" v-show="hasMoreNext">
<span>...</span>
</li>
<!-- Show last page -->
<li
class="page-item"
v-if="lastPage"
:class="{ active: page === lastPage }"
>
<a href="javascript:void(0)" @click="handlePageItemClick(lastPage)">
{{ lastPage + 1 }}
</a>
</li>
<li class="page-item" :class="{ disabled: !hasNext }">
<a href="javascript:void(0)" @click="handleNextClick">Next</a>
</li>
</ul>
</div>
</template>
<script>
export default {
name: "Pagination",
model: {
prop: "page",
event: "change"
},
props: {
page: {
type: Number,
required: false,
default: 0
},
size: {
type: Number,
required: false,
default: 10
},
total: {
type: Number,
required: false,
default: 0
}
},
data() {
return {
middleSize: 5
};
},
computed: {
pages() {
return Math.ceil(this.total / this.size);
},
hasNext() {
return this.page < this.pages - 1;
},
hasPrev() {
return this.page > 0;
},
firstPage() {
if (this.pages === 0) {
return null;
}
return 0;
},
hasMorePrev() {
if (this.firstPage === null) {
return false;
}
return this.page - 2 > this.firstPage;
},
hasMoreNext() {
if (this.lastPage === null) {
return false;
}
return this.page + 2 < this.lastPage;
},
middlePages() {
if (this.pages <= 2) {
return [];
}
if (this.pages <= 2 + this.middleSize) {
return this.range(1, this.lastPage);
}
const halfMiddleSize = Math.floor(this.middleSize / 2);
let left = this.page - halfMiddleSize;
let right = this.page + halfMiddleSize;
if (this.page <= this.firstPage + halfMiddleSize + 1) {
left = this.firstPage + 1;
right = left + this.middleSize - 1;
} else if (this.page >= this.lastPage - halfMiddleSize - 1) {
right = this.lastPage - 1;
left = right - this.middleSize + 1;
}
return this.range(left, right + 1);
},
lastPage() {
if (this.pages === 0 || this.pages === 1) {
return 0;
}
return this.pages - 1;
}
},
methods: {
handleNextClick() {
if (this.hasNext) {
this.$emit("change", this.page + 1);
}
},
handlePrevClick() {
if (this.hasPrev) {
this.$emit("change", this.page - 1);
}
},
handlePageItemClick(page) {
this.$emit("change", page);
},
range(left, right) {
if (left >= right) {
return [];
}
const result = [];
for (let i = left; i < right; i++) {
result.push(i);
}
return result;
}
}
};
</script>
<style>
.pagination {
justify-content: center;
}
</style>
Share
在 Ubuntu 18.04 上建立 WireGuard 隧道组建 VPS 大内网