【题解】洛谷 P7286 「EZEC-5」人赢

wsyhb · 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;
}