【题目描述】
给定一个长度为 \(n\) 的数列,其中每个元素互不相同,进行 \(k\) 次操作,每次可以选择删除序列中最小的两个数或最大的一个数。求操作后剩余数的和的最大值。
【思路】
我们构造一组数据:
首先我们看到题目中的一句话:每次可以选择删除序列中最小的两个数或最大的一个数。
,说明要对数组的最大值、最小值进行访问,于是考虑排序:
假设我们现在的 \(k\) 是 \(3\),那么我们可以有以下几种删数的方法:
-
删三次最大值:
-
删两次最大值,一次最小值
-
删一次最大值,两次最小值
-
删三次最小值
我们发现了什么? 每一种删法都是删一段小元素,删一段大元素!我们可以使用前缀和先预处理一下,就可以求出剩下元素的和了。
代码 \(O(n)\) 复杂度:
#include <bits/stdc++.h>
using namespace std;
long long ans,a[1000005];
long long sum[1000005];
int T,n,k;
int main()
{
scanf("%d",&T);
while(T--)
{
ans=0;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
sum[i]=a[i]+sum[i-1];
}
for(int i=0;i<=k;i++){//枚举取多少个最大值
ans=max(ans,sum[n-(k-i)]-sum[i*2]);
}
printf("%lld\n",ans);
}
return 0;
}
标签:CF1832B,int,题解,Sum,元素,long,最小值,最大值
From: https://www.cnblogs.com/Sundar-2022/p/18031238