首页 > 其他分享 >CF1832B Maximum Sum 题解

CF1832B Maximum Sum 题解

时间:2024-02-24 16:46:33浏览次数:31  
标签:CF1832B int 题解 Sum 元素 long 最小值 最大值

【题目描述】

给定一个长度为 \(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

相关文章

  • P4569 [BJWC2011] 禁忌 题解
    题目传送门前置知识AC自动机|矩阵加速递推解法对于一段固定的文本串,由于重叠的模式串不对伤害产生贡献,故考虑贪心,每碰到出现一个模式串将其分为一段,最终这个文本串的伤害就是划分次数。类似luoguP3193[HNOI2008]GT考试,令\(f_{i,j}\)表示前\(i\)个字符,当前运行到......
  • pytest简易教程(33):pytest常用插件 - 多重校验(pytest-assume)
     pytest简易教程汇总,详见:https://www.cnblogs.com/uncleyong/p/17982846应用场景对同一用例,要执行多个断言,查看断言是否都成功哪怕某个断言失败,后面断言依然能执行(assert实现不了) 插件安装pipinstall pytest-assume 使用方式pytest.assume(表达式)如果使用assert......
  • AT_abc341_g [ABC341G] Highest Ratio 题解
    题目传送门前置知识单调栈简化题意给定一个长度为\(n\)的序列\(a\)。对于所有的\(l(1\lel\len)\),均求出\(\max\limits_{r=l}^{n}\{\frac{\sum\limits_{i=l}^{r}a_{i}}{r-l+1}\}\)。解法令\(sum_{i}=\sum\limits_{j=1}^{i}a_{j},P_{i}=(i,sum_{i})\),则有\(\beg......
  • P10139 [USACO24JAN] Nap Sort G 题解
    DescriptionBessie正在尝试使用她自己的排序算法对一个整数数组进行排序。她有一堆共\(N\)(\(1\leN\le2\cdot10^5\))个整数\(a_1,a_2,\ldots,a_N\)(\(1\lea_i\le10^{11}\)),她将会按排序顺序将这些数放入一个单独的数组中。她反复查找这堆数中的最小数,将其删除,同时将其添加到......
  • UOJ228/HDU5828 基础数据结构练习题/Rikka with Sequence 题解(势能线段树)
    势能线段树。如果线段树上一个节点的\(\max-\min\ge2\),我们称其为关键节点,考虑定义势能\(\phi\)为线段树上关键节点的个数。对于每次开方操作,如果当前节点为关键节点,则暴力递归左右儿子修改,否则:如果当前节点\(\max=\min\)或\(\max=\min+1\)且\(\max\)不是完全平方数,......
  • UVA12421 (Jiandan) Mua (I) - Lexical Analyzer 题解
    蒟蒻的第一篇紫题题解!题目传送门思路一眼模拟,还是大模拟。不由得想起了我编了\(4\)个小时的猪国杀……输入首先处理输入,这里我们用一个字符串数组来存储所有的输入,然后再进行处理。while(getline(cin,sr))str[++cnt]=sr+'\n';处理时需要双重循环,注意如果遍历到空格要跳......
  • CF916E Jamie and Tree 题解
    题目链接:CF或者洛谷本题难点在于换根LCA与换根以后的子树范围寻找,重点讲解先说操作一,假如原根为\(1\)变为了\(x\),又变为了\(y\),那么其实\(y\)和\(x\)都可以看做由\(1\)变化而来的,即\(1\rightarrowx\)与\(1\rightarrowy\),原因很简单,我们可以把\(1\rightar......
  • P9901 『PG2』弯曲半平面直线同向图最大流 题解
    思路正解想不出,只好用网络流了网络流简介请戳这儿。这道题数据有点大用EK求最大流似乎过不了,所以本蒟蒻采用Dinic算法。Dinic算法Dinic算法相当于EK的优化。在原基础找增广路的基础上添加了一个分层操作,再通过深搜找阻塞流。分层从原点开始我们把可以通过一步到达的......
  • 记录pyinstaller 打包 pdfplumber 问题解决过程
    今天有一个pdf文件处理需求,使用pdfplumber库完成,python环境是3.11+win10pyinstaller5.10.1打包完成后,工具可以顺利打开,但是执行处理的时候报错File"pypdfium2_raw\bindings.py",line93,in<module>File"pypdfium2_raw\bindings.py",line83,in_register_library......
  • blazor 问题解决
    Cannotprovideavalueforproperty'ScrollToLocationHash'ontype'Microsoft.AspNetCore.Components.Routing.Router'.Thereisnoregisteredserviceoftype'Microsoft.AspNetCore.Components.Routing.IScrollToLocationHash'.异常信息......