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}

。

CPP

#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)

。

CPP

#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;
}

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

文章操作

0x00 暴力 1

0x01 暴力 2

0x02 正解

相关推荐

评论

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