题解：P14306 【MX-J27-T3】旋律

· · 题解

0x00 暴力 1

考虑 dfs 枚举， 此时时间复杂度：O(2^N\times N)。

期望得分：\red{20}。

0x01 暴力 2

注意到题目所求的为子序列而非子段，所以可以升序排序。

所以 \max(a_1,\ldots,a_n)=a_n，同理，\min(a_1,\ldots,a_n)=a_1。

然后发现“极差”为最大值减去最小值，所以最大值和最小值差距越小越好，又因为最后的“和谐度”又与 k \times len（len 为序列长度）有关，所以容易想到枚举区间 [l,r] 则该区间“和谐度”计算式为：(r-l+1) \times k-(a_r-a_l)。

此时时间复杂度：O(N^2)。

期望得分：\red{55}。

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N=1e5+5;

int a[N];

signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
  int t,n,k,ans;
  cin>>t>>t;
  while(t--){
    cin>>n>>k;
    ans=-1e18;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            ans=max(ans,(j-i+1)*k-(a[j]-a[i]));
        }
    }
    cout<<ans<<'\n';
  }
  return 0;
}

0x02 正解

设 r 固定，则可以将答案表达式 \max\{k \times (r-l+1)-(a_r-a_l) \} 中含 r 的项提出，则可得当右端点固定时的最大值表示为：k \times (r+1)-a_r+ \max \{a_l-k \times l\}，注意到此时可以在枚举 r 的同时处理 \max \{a_l-k \times l\}，此时时间复杂度与排序相同，为 O(N\log N)。

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N=1e5+5;

int Read(){//快读
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}

void Put(int x){//快写
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else Put(x/10),putchar(x%10+'0');
}

int a[N];

signed main(){
    int t,n,k,ans,Max;
    t=Read();
    t=Read();
    while(t--){
        n=Read();
        k=Read();
        ans=-1e18,Max=-1e18;//注意答案可能为负数，所以要初始化为极小值
        for(int i=1;i<=n;i++){
            a[i]=Read();
        }
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++){
            if(Max<(a[i]-i*k)){//（可能是觉得max()太慢了，所以改了if
                Max=a[i]-i*k;
            }
            ans=max(ans,(i+1)*k-a[i]+Max);
        }
        Put(ans);
        puts("");
    }
    return 0;
}