首页 > 试题广场 >

某环形公路上有N个站点，分别记为A1......An，从Ai

[问答题]

某环形公路上有N个站点，分别记为A1......An，从Ai到A（ i+1）的距离为Di。An到A1的距离为Do，假设Do=Dn=1，保存在数组D（N）中，现在要求你与一个函数，能够高效的计算出公路上任意两点的最近距离，要求空间复杂度不能超过O(N)。

const int N=100;
double D(N);
...
Void preprocess(){
//Write your code here,        (1)
}
double Distance(int i, int j){
// Write your code bere         (2)
}

推荐

牛客630575号

#include"iostream"
#include"math.h"
#define MAX 100
using namespace std;
int main(int argc, char* argv[])
{
    int N;
    double D[MAX],sum=0,SumD[MAX];
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>D[i];
        sum+=D[i];
        SumD[i] = sum;
    }
    while(true)
    {
        int a,b;
        cin>>a>>b;
        if(a>N||b>N)
            break;
        float temp = fabs(SumD[a-1]-SumD[b-1]);
        cout<<"result: "<<(temp>(sum-temp)?(sum-temp):temp)<<endl;
    }
    return 0;
}

编辑于 2015-02-06 14:18:50 回复(0)

CCoder

<pre class="prettyprint lang-cpp"> <div class="line number1 index0 alt2" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> constintN=100; </div> <div class="line number2 index1 alt1" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> doubleD(N); </div> <div class="line number4 index3 alt1" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> Void preprocess(){ </div> <div class="line number4 index3 alt1" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> </div> <div class="line number4 index3 alt1" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> double sum[N]; </div> <div class="line number4 index3 alt1" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> sum[0]=0; </div> <div class="line number4 index3 alt1" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> for(int i=0;i<N;i++) </div> <div class="line number4 index3 alt1" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> sum[i]+=D[i]; </div> <div class="line number6 index5 alt1" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> } </div> <div class="line number7 index6 alt2" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> doubleDistance(inti, intj){ </div> <div class="line number7 index6 alt2" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> </div> <div class="line number7 index6 alt2" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> if (i<1||j<1||i>N||j>N) </div> <div class="line number7 index6 alt2" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;">    return null; </div> <div class="line number7 index6 alt2" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> if(i==j) </div> <div class="line number7 index6 alt2" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;">    return 0; </div> <div class="line number7 index6 alt2" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> if(i>j) </div> <div class="line number7 index6 alt2" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;">     return min(sum[i-1]-sum[j-1],sum[N-1]-(s<span>um[i-1]-sum[j-1]</span><span style="color:#000000;">)</span><span style="color:#000000;">);</span> </div> <div class="line number7 index6 alt2" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> <span style="color:#000000;">else return min(sum[j-1]-sum[i-1],sum[N-1]-(sum[j-1]-sum[i-1]))</span> </div> <div class="line number7 index6 alt2" style="color:#333333;margin:0px !important;padding:0px 1em !important;vertical-align:baseline !important;"> <span style="color:#000000;">}</span> </div> </pre> <br />

发表于 2015-08-16 09:39:09 回复(0)

xxj

double A[N];
void Preprocess () {
double sum = 0;
for ( int i = 0; i < N; ++i ) {
sum += D[i];
A[i] = sum;
}
}
double Distance ( int i, int j ) { // i : 1 ~ N, j : 1 ~ N
if (i < 1 || j < 1 || i > N || j > N )
return -1; // illegal input
if (i == j)
return 0.0;
if (i > j)
std::swap (i, j);
return min (A[j-1] - A[i-1], A[N-1] - (A[j-1] - A[i-1]));
}

发表于 2014-11-27 09:37:29 回复(0)

小小

预先计算出每个点离最左和最右的距离

发表于 2014-11-01 22:51:35 回复(0)

提交观点

问题信息

谷歌复杂度

来自：Google2012笔试卷

上传者：浪野天涯

难度：

4条回答 17收藏 8461浏览

某环形公路上有N个站点，分别记为A1......An，从Ai

问题信息

热门推荐

相关试题