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 大内网

https://nova.moe/deploy-wireguard-on-ubuntu-bionic/