arts    

ARTS-w002

314 次访问
johnniang
Scroll Down

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/

© 本文著作权归作者所有，转载前请务必署名
最新文章
Protocol Buffer - proto3 指南

此前对ProtocolBuffer有了初步的了解，接下来我们需要学会proto3的消息是如何定义的。定义消息类型首先，我们从一个非常简单的例子入手。通常我们在设计查询接口参数的时候，会包含关键字（query）、页码（page_number）和每页的结果数（
Protocol Buffer 简介

最近阅读Skywalking源码的时候发现，SkywalkingTrace的数据都是通过protobuf协议来通信的，在继续阅读源码前，想简单了解ProtocolBuffer。喜欢阅读英文文档的读者可以考虑直接查看官方网站：https://develope
Redis 数据类型介绍

通过上一篇对Redis的简单介绍，想必对Redis的认知有了一个整体的把握。接下来我们将会一一介绍Redis所支持的数据类型。概览Redis并不是一个普通的键-值存储器，它实际上是一个数据结构服务器，支持多种类型的值。这就意味着，尽管在传统的键-值存储中，
Redis 简介

概览本篇博文主要是为了简单介绍Redis。以下内容翻译自：https://redis.io/topics/introduction介绍Redis是一个开源（BSD许可）的，基于内存的数据结构存储，且被用作数据库，缓存和消息代理。它支持数据类型有：strin
JVM 常用参数详解（译）

概览 本篇博文中将会探索一些常用的 JVM Options。 显示指定堆内存参数：-Xms 和 -Xmx 常用的性能相关实践就是应应用程序的需求来初始化堆内存。下面两个个参数可以用于指定最小和最大堆内存。 -Xms<heap size>[uni
分类
Protocol Buffer
Redis
Linux
Java 重拾
Spring
ARTS
Java
标签
protobuf
redis
cache
poc
halo
record
pat
shell
original
docker
spring
solution
input method
linux
java
arts