P8311题解

_Give_up_ · 2022-05-29 16:14:31 · 题解

思路

从题目中，我们不难看出，对于每一个 d[i] 都至少用了一次。我们特判如果 n = 1，直接输出 0，结束程序。否则让所有车库都与 d[i] 最小的车库相连即可，我们从 0 循环到 n，计算所有 d[i] 的和，用 k 做变量，再找 d[i] 的最小值，用 ans 做变量。 最后一步，用 k + n \times ans-2 \times ans，化简后就是 k+(n-2) \times ans。

代码

#include<bits/stdc++.h>
#define N 1000010

using namespace std;

typedef long long ll;

ll read()
{
    ll x = 0,f = 1;
    char c = getchar();
    while(c<'0' || c>'9')
    {
        if(c=='-') f = -1;
        c = getchar();
    }
    while(c>='0' && c<='9')
    {
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
    return x*f;
}

ll a[N];

int main()
{
    ll n = read();
    for(int i=1;i<=n;i++)
        a[i] = read();
    if(n==1)
    {
        printf("%d\n",0);
        return 0;
    }
    ll sum=0,ans = 1000000000000;
    for(int i=1;i<=n;++i)
    {
        sum += a[i];
        ans = min(a[i],ans);
    }
    printf("%lld\n",sum+(n-2)*ans);
    return 0;
}

最后说一句，一定要开 long long。