自动搬运

查看原文

来自洛谷，原作者为

	wsyhb **

搬运于2025-08-24 22:28:25，当前版本为作者最后更新于2021-01-23 21:31:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析 + 题解

首先，$x=y$ 的情况仅有 $n$ 种，枚举 $x$ 即可更新答案。

其次，对于 $x \neq y$ 的情况，$f(x,y)=\min(k_x,k_y) \cdot (x+y)$。我们按 $k$ 值从大到小对编号排序，记排序后第 $i$ 个编号为 $p_i$（$k_{p_1} \geq k_{p_2} \geq \cdots \geq k_{p_n}$），则 $\max_{x \neq y}f(x,y)=\max_{i=1}^n [k_i \cdot (i+\max_{j=1}^{i-1} p_j)]$，也就是枚举其中 $k$ 较小的位置的编号 $p_i$，则另外一个编号为 $p_1,p_2,\cdots,p_{i-1}$ 中的一个，记录前缀 $\max$ 即可线性计算。

时间复杂度：$O(n\log n)$（因为需要排序）

代码

实际实现时，可将前缀 $\max$ 初始值赋为 $0$，相当于 $x=y$，即可按照 $x\neq y$ 的情况直接计算。

#include<bits/stdc++.h>
using namespace std;
const int max_n=1e6+5;
int k[max_n],id[max_n];
inline bool cmp(int x,int y)//按 k 值从大到小对编号排序 
{
	return k[x]>k[y];
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",k+i);
		id[i]=i;
	}
	sort(id+1,id+n+1,cmp);
	int Max=0;
	long long ans=0;//记得开 long long 
	for(int i=1;i<=n;++i)
	{
		ans=max(ans,1ll*k[id[i]]*(id[i]+Max));
		Max=max(Max,id[i]);//注意要先更新 ans 再更新 Max 
	}
	printf("%lld\n",ans);
	return 0;
}