公共交通问题

迷南。 2023-02-23 05:24 25阅读 0赞

## 公共交通问题 ##

现在的大学生刚毕业不久如果没有家庭的支持一般是买不起心仪的车的，所以刚毕业的人一般都要乘公交车上下班，在早晚的上下班高峰时间段，道路交通很拥挤，每站都有人上下，公交车在每站都停。刚刚毕业的小明常常会被每站都停的公交车弄得很不耐烦，于是他提出了这样一个办法：

由于公交车的站点并不是非常多，那么在繁忙的上下班高峰时间，每次公交车从始发站点往终点站点开时，我们只允许公交车停在其中的某一个站点。所有乘客都从始发站点上公交车，到达某站点后，公交车停下来，所有乘客再从这里步行到自己的目的站点。在始发站的时候，每个乘客选择自己的目的站点，公交车系统则自动计算出应停的站点。

现在请问：公交车停在哪一站点能够保证这次乘坐公交车的所有乘客步行的站点数之和最少？

在这里为了更好体现算法的魅力所在，我们假定站点数可以很多，每次乘客人数也可以很多（实际生活中这两点是不可能出现的）。另外为了方便起见，在这里我们规定，刚开始公交车在始发站，并且认为乘客至少是在第一个站点及以后才有可能下车。

**Input**

有两行，第一行是公交站点数N（1<=N<=1000），第二行是N个正整数，分别表示对应站点（以该站点作为目的站点）的乘客人数M（1<=M<=1000）。

**Output**

只有一行，输出两个正整数，第一个是计算出来的公交车停靠的站点，第二个是所有乘客需要步行的站点总数，中间有一个空格。如果公交车在不同站点停车都可以让乘客步行站点最少的话，则公交车会停在最先到达的站点，这样可以省些油和时间。

本问题有多组测试数据。

**Sample Input**

5
    14 12 2 18 15
    6
    4 9 0 16 16 12

**Sample Output**

4 83
    4 70

## 代码 ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int a[1010];
    int main()
    {
        
        int n;
        while(cin>>n)
        {
        
            for(int i=1;i<=n;i++)
            {
        
                scanf("%d",&a[i]);
            }
            int ans=INT_MAX;
            int pos=0;
            for(int i=1;i<=n;i++)
            {
        
                int cnt=0;
                for(int j=1;j<=n;j++)
                {
        
                    cnt+=a[j]*(abs(j-i));
                }
                if(cnt<ans)
                {
        
                    ans=cnt;
                    pos=i;
                }
            }
            cout<<pos<<' '<<ans<<endl;
    
        }
    
        return 0;
    }