P3819 松江1843路

题目描述

涞坊路是一条长L米的道路，道路上的坐标范围从0到L，路上有N座房子，第i座房子建在坐标为x[i]的地方，其中住了r[i]人。

松江1843路公交车要在这条路上建一个公交站，市政府希望让最多的人得到方便，因此希望所有的每一个的居民，从家到车站的距离的总和最短。

公交站应该建在哪里呢？

输入输出格式

输入格式：

第一行输入L、N。

接下来N行，每行两个整数x[i]和r[i]。

输出格式：

一个整数，最小的每个人从家到车站的距离的总和。

输入输出样例

输入样例#1：复制

输出样例#1：复制

输入样例#2：复制

输出样例#2：复制

输入样例#3：复制

10000000000 5

3282894320 391

4394338332 929

6932893249 181

7823822843 440

9322388365 623

输出样例#3：复制

5473201404068

说明

样例解释1

当建在坐标40的时候，所有人距离车站的距离总和为 |20−40|×3+|50−40|×2+|70−40|×1=110。

数据范围和约定

对于10%的数据，1≤N≤50，R[i]=1。

对于30%的数据，1≤N≤100，R[i]≤10，1≤L≤1000。

对于70%的数据，1≤N≤1000，R[i]≤100，1≤L≤10^6。

对于全部数据，1≤L≤10^10，1≤N≤10^5，0≤x[i]≤L，1≤r[i]≤1000

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#define maxn 100010

using namespace std;

int L,n,x[maxn],r[maxn],mx;

long long sum[],ans=;

int main(){

    scanf("%d%d",&L,&n);

    for(int i=;i<=n;i++)scanf("%d%d",&x[i],&r[i]),mx=max(mx,x[i]);

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

        for(int j=;j<=mx;j++)

            sum[j]+=1LL*abs(x[i]-j)*r[i];

    for(int i=;i<=mx;i++)ans=min(ans,sum[i]);

    cout<<ans;

}

70分暴力

#include<iostream>

#include<cstdio>

#define maxn 100010

using namespace std;

long long L,n,sumxr[maxn],sumr[maxn],minn=((long long)<<)-,ans;

using namespace std;

struct node{long long r,x;}q[maxn];

int main(){

    cin>>L>>n;

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

        cin>>q[i].x>>q[i].r;

        sumxr[i]=sumxr[i-]+q[i].x*q[i].r;

        sumr[i]=sumr[i-]+q[i].r;

    }

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

        ans=sumxr[n]-sumxr[i]*+q[i].x*(*sumr[i]-sumr[n]);

        minn=min(ans,minn);

    }

    cout<<minn;

    return ;

}

100分三分

巴特西

洛谷P3819 松江1843路

P3819 松江1843路

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章