多么恶心的题

免责声明

本篇题解所写内容均为个人想法，并不代表且可能完全与代老师的标准思路、答案无关。若遇到此种情况，以英明神武帅气的代老师的代码为准。本人代码仅供参考。

闪耀的数

题目大致描述：给定一串数字，求出该串数字中某一重复数字的闪耀值。 “ai 的闪耀值为所有和 ai 相等的数到 ai的距离之和” 说白了就是算距离。

基本思路

1.54分为一条分界线。该54分可以由纯暴力得出，基本不需要任何额外的考虑。代码如下： (话说题目里不是60%的数据吗，怎么成54分了（恼））

O(n^2)的时间复杂度仅适用于前60%的数据不会超时。

#include<bits/stdc++.h>
using namespace std;
int n,a[100010];
//bool pd[100010];
long long da=0;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
	{//从头开始枚举，判断距离
		long long sum=0;
		for(int j=1;j<=n;j++)
		{
			if(a[j]==a[i])
				sum+=abs(j-i);
		}
		da=max(da,sum);//da存储最大距离
	}
	cout<<da;
	return 0;
}

2.剩下的46分就需要动一动脑子了，也不怎么牵扯算法，但是需要考虑一点数学问题。

不严谨的证明：若从ABC当中任选一点，计算另外两点到该点距离的和，易证只有选取端点时加和最多，例如选取A点则为AB+AC=a+a+b=2a+b;（类似于等差数列求和） 若选取B点则距离和为a+b，明显小于上述答案。

所以！

我们仔细观察题目中的数据，a[i]<=100诶，那我们就可以从这个100入手，把代码优化一下。诚如上方的样例，因此我们对于一组相同的数字只需要判断两次，一次是从头判断距离和，一次是从尾判断。以后再遇到这个数字就不需要判断了。最多只需要判断100次，可以理解为某种计数算法。

因此上面的纯暴力算法就可以小小的剪枝一下，原本的时间复杂度为O(n^2)，优化后……应该是O(100n），因为只有100个数，执行100次就可以得出结果了……emmm，本人对于时间复杂度的学习并不怎么认真，这块看看就好。

上代码！（其余的在代码里打注释）

#include<bits/stdc++.h>
using namespace std;
int n,a[100010];
bool pd[150]; //标记数组，标记某数字是否被计算过 
long long da=0;  //记录答案 
long long search(int le,int ri,int num)  //用于搜索计算距离之和的函数 
{
	long long re1=0,re=0;
	for(int i1=le;i1<=ri;i1++)
		if(a[i1]==num)
			re+=abs(i1-le);  //从头到尾枚举一次 
	for(int i1=ri;i1>=le;i1--)
		if(a[i1]==num)
			re1+=abs(i1-ri);  //从尾到头枚举一次 
	return max(re,re1);  //返回最大值 
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];   //输入数据 
	for(int i=1;i<=n;i++)
	{
		if(pd[a[i]]==0) //如果当前的数字没有被计算过 
		{
			int head,tail;  //定义每一个头、尾指针，指向每一组数据的头尾 
			head=i;  //让头指针等于当前的位置 
			pd[a[i]]=1;  //标记该数字已经计算过 
			for(int j=1;j<=n;j++)
				if(a[j]==a[i]) 
					tail=j; //向后遍历查找，使得尾指针指向最后一个相同的数字 
			long long sum=search(head,tail,a[i]);  //调用搜索计算函数 
			da=max(da,sum);  //保存最大值 
		}
	}
	cout<<da;  //输出答案 
	return 0;
}

注意，保存答案的变量要开longlong （最后一组数据就是坑人数据） 因为题目中的n<=100000，而从1-100000的等差数列加和大于了int型的范围。

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 的数的位置。

vector<int> a[105]; //a[i] 储存所有大小为 i 的数的位置。

对于同一种颜色的数，显然最左边或最右边的数闪耀值最大，因此分别计算 a[i][0] 与 a[i][a[i].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;