1046 Shortest Distance (20)（20 分）提问

The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.

Input Specification:

Each input file contains one test case. For each case, the first line contains an integer N (in [3, 10⁵]), followed by N integer distances D₁ D₂ ... D_N, where D_i is the distance between the i-th and the (i+1)-st exits, and D_N is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (<=10⁴), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 10⁷.

Output Specification:

For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

Sample Input:

5 1 2 4 14 9

3

1 3

2 5

4 1

Sample Output:

思考

这里面c++的解法用到了头文件algorithm

纯C语言可以使用algorithm头文件，因为algorithm是C++库里的 algorithm中的大部分算法都是针对C++语言特有的，需要用到STL（标准模板库）的容器等。具体可以参考：https://en.wikipedia.org/wiki/Algorithm_(C%2B%2B) 纯C语言可以在网上找一些第三方的库去替代，但是灵活性肯定是比C++的标准库提供的方法低很多，因为语言本身的局限性。

交换和求较小值

/*交换两个整数值*/

myswap(int *a,int *b){

    int *temp;

    temp=a;

    a=b;

    b=temp;

}//这个交换对外界的那两个left与right没有影响

/*交换修正版*/

myswap(int *a,int *b){

    int temp;

    temp=*a;

    *a=*b;

    *b=temp;

}/*传入指针，就能修改这个值本身*/

/*求两整数较小值*/

int mymin(int a,int b){

    return (a>b)?b:a;

}

AC代码

#include <stdio.h>

#define max 100005

int dis[max], A[max];

/*交换两个整数值*/

myswap(int *a,int *b){

    int temp;

    temp=*a;

    *a=*b;

    *b=temp;

}//还是有疑惑的

/*求两整数较小值*/

int mymin(int a,int b){

    return a>b?b:a;

}

int main() {

    int sum = 0, query, n, left, right;

    scanf("%d", &n);

    for(int i = 1; i <= n; i++) {

        scanf("%d", &A[i]);

        sum += A[i];

        dis[i] = sum;//存入了顺时针从1号点到i+1号点的距离

    }

    scanf("%d", &query);

    for(int i = 0; i < query; i++) {

        scanf("%d%d", &left, &right);

        if(left > right) myswap(&left, &right);

        int temp = dis[right - 1] - dis[left - 1];

        printf("%d\n", mymin(temp, sum - temp));

    }

    return 0;

}

巴特西

A1046 Shortest Distance (20)（20 分）

1046 Shortest Distance (20)（20 分）提问

思考

交换和求较小值

AC代码

最新文章

热门文章