100分 要使a[i]距离之和最小，则位置必定位于与a[i]相同的数的最左与最右之间；反之，要使a[i]距离之和最大，则位置必定位于最左或最右，因此枚举时只需要计算最左与最右的距离之和就行了。 这个方法也许没有楼上的100分做法好，但是代码绝对是更容易理解的。

#include<bits/stdc++.h>
using namespace std;
int n;
long long ans, x;
short a[100005], vis[105];

这边答案为ans，x为每次计算的距离和，long long防止越界。 vis数组用于记录是否遇到过a[i]，因为是从左到右枚举，所以第一个遇到的a[i]必定是最左边的a[i]。 遇到第一个a[i]后即a[i]++以记录用过。 short类型速度会比int快而且占用空间比int小，上限是我的世界的附魔等级上限哦~

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        x = 0;
        if (vis[a[i]])continue;
        for (int j = 1; j <= n; j++) {
            if (a[j] == a[i] && i != j) {
                x += abs(i - j);
            }
        }
        vis[a[i]]++;
        ans = max(ans, x);
    }
    for (int i = n; i >= 1; i--) {
        x = 0;
        if (vis[a[i]] != 1)continue;
        for (int j = n; j >= 1; j--) {
            if (a[j] == a[i] && i != j) {
                x += abs(i - j);
            }
        }
        vis[a[i]]++;
        ans = max(ans, x);
    }
    cout << ans << "\n";
    return 0;
}

60 分

对于 $60\%$ 的数据，因为 $n\le 1000$，所以可以直接使用 $O(n^2)$ 的算法暴力枚举。

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100000 + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        long long now = 0;
        for (int j = 1; j < i; j++)
            if (a[i] == a[j])
                now += i - j;
        for (int j = i + 1; j <= n; j++)
            if (a[i] == a[j])
                now += j - i;
        ans = max(ans, now);
    }
    cout << ans << endl;
    return 0;
}

对于 $100\%$ 的数据，$n\le 100000$，$O(n^2)$ 的算法就跑不动了。

100 分做法 1

观察题面，容易发现每个数只需要管与自己相等的数的位置，因此可以把同一种颜色的数放在一起，比如使用 a[i] 储存所有大小为 i 的数的位置。

对于同一种颜色的数，显然最左边或最右边的数闪耀值最大，因此分别计算 a[i][0] 与 a[i][a.size()-1] 的闪耀值即可。

cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        a[x].push_back(i);
    }
    long long ans = 0;
    for (int i = 1; i <= 100; i++)
    {
        if (a[i].size() < 2)
            continue;
        //a[i][0] 的闪耀值
        long long now1 = 0;
        for (int j = 1; j < a[i].size(); j++)
            now1 += a[i][j] - a[i][0];
        //a[i][a.size()-1]的闪耀值
        long long now2 = 0;
        for (int j = 0; j < a[i].size() - 1; j++)
            now2 += a[i][a[i].size() - 1] - a[i][j];
        ans = max(ans, now1);
        ans = max(ans, now2);
    }
    cout << ans << endl;

100 分做法 2

我们还可以对每一个数 a[i]，统计前面出现的次数 cnt[a[i]]，上一个相等的数的位置 last[a[i]]，以及上一个相等的数由之前的数产生的闪耀值 now[a[i]]。

那么显然当前的数由之前的数产生的闪耀值为：now[a[i]] + cnt[a[i]] * abs(i - last[a[i]])。

正着扫一遍，再反着扫一遍即可。

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    long long ans = 0;
    //前->后
    memset(last, 0, sizeof(last));
    for (int i = 1; i <= n; i++)
    {
        if (last[a[i]] == 0)
        {
            last[a[i]] = i;
            cnt[a[i]] = 1;
            now[a[i]] = 0;
        }
        else
        {
            now[a[i]] += (i - last[a[i]]) * cnt[a[i]];
            last[a[i]] = i;
            cnt[a[i]]++;
        }
        ans = max(ans, now[a[i]]);
    }
    //前<-后
    memset(last, 0, sizeof(last));
    for (int i = n; i >= 1; i--)
    {
        if (last[a[i]] == 0)
        {
            last[a[i]] = i;
            cnt[a[i]] = 1;
            now[a[i]] = 0;
        }
        else
        {
            now[a[i]] += (last[a[i]] - i) * cnt[a[i]];
            last[a[i]] = i;
            cnt[a[i]]++;
        }
        ans = max(ans, now[a[i]]);
    }
    cout << ans << endl;

测试通过，100分答案

运用二维数组

#include
using namespace std;
long long n,x,a[101][100001],sum[101],sum2,ans;
int main()
    {
    cin >> n;
    for (int i = 1;i <= n;i++)
    {
        cin >> x;
        a[x][++sum[x]] = i;
    }
    for (int i = 0;i <= 100;i++)
    {
        if (sum[i] > 1)
        {
            sum2 = 0;
            for (int j = 2;j <= sum[i];j++)
            {
                sum2 += a[i][j] - a[i][1];
            }
            ans = max(ans,sum2);
            sum2 = 0;
            for (int j = 1;j < sum[i];j++)
            {
                sum2 += a[i][sum[i]] - a[i][j];
            }
            ans = max(ans,sum2);	
        }
    }
    cout << ans;
    return 0;
}

思路：

• 相同数才可以求出闪耀值，所以使用二维动态数组来保存
• 将数字输入数组的下标，把相同数字的下标存储在一起
• a的闪耀值为所有和a相同的数的距离之和对于同一种颜色的数要求最大的闪耀值，显然最左边或最右边的数闪耀值最大
• 所以可以让最左边的数依次减去剩下的数求闪耀值，再让最右边的数依次减去剩下的数求闪耀值
• 两者找最大

代码：

省略

一开始先输入并将相等的数的位置记录在一个数组内，再看左边闪耀值大还是右边闪耀值大

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,a[100005],num[107],d[107][100007];
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    long long maxx=0;
    for (int i=1;i<=n;i++)
        d[a[i]][++num[a[i]]]=i;
    for (int i=1;i<=100;i++)
    {
        long long sum=0;
        for (int j=2;j<=num[i];j++)
            sum+=abs(d[i][1]-d[i][j]);
        maxx=max(maxx,sum);
        sum=0;
        for (int j=1;j<num[i];j++)
            sum+=abs(d[i][num[i]]-d[i][j]);
        maxx=max(maxx,sum);
    }
    cout<<maxx;
    return 0;
}

显而易见， 1.一个数到其他所有数的和=到左边所有数的和+到右边所有数的和
2. 设ox表示左边一个和ai同色的数的下标，则(i-o1)+(i-o2)+……+(i-on)=i*n-o1+o2+……+on,可以用前缀和ls、后缀和rs统计o1+o2+……+on，再开两个数组统计当前的n（即左边同色数量ln、右边同色数量rn）

输入
for (int i = 1; i <= n; i++)
{
    f[i] += ln[a[i]] * i - ls[a[i]];
    ls[a[i]] += i;
    ln[a[i]]++;
}//正着扫一遍
for (int i = n; i >= 1; i--)
{
    f[i] += rs[a[i]] - rn[a[i]] * i;
    rs[a[i]] += i;
    rn[a[i]]++;
}//反着扫一遍
for (int i = 1; i <= n; i++)
    ans = max(ans, f[i]);
cout << ans;
    return 0;

从前往后扫一遍，再从后往前扫一遍

#include <iostream>
using namespace std;
int main()
{
    long a[100005],max=0,n,first,s=0;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=1;i<=100;i++){
        s=0;
        first=100006;
        for(int j=0;j<n;j++){
            if(a[j]==i){first=j;break;}
        }
        if(first>=100000)continue;
        for(int j=first+1;j<n;j++){
            if(a[j]==i)s+=j-first;
        }
        if(s>max)max=s;
    }
    for(int i=1;i<=100;i++){
        s=0;
        first=-1;
        for(int j=n-1;j>=0;j--){
            if(a[j]==i){first=j;break;}
        }
        if(first<0)continue;
        for(int j=first;j>=0;j--){
            if(a[j]==i)s+=first-j;
        }
        if(s>max)max=s;
    }
    cout<<max;
    return 0;
}

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
}

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。