首页 > 其他分享 >contest/1921 D Very Different Array

contest/1921 D Very Different Array

时间:2024-01-24 22:13:03浏览次数:23  
标签:Different val Very 端的 选择 1921 数组 左端

很容易看的出来是一个贪心。

首先对A,B数组进行排序。

我猜测的结论是每次从A数组和B数组中的两端选择,分别得到:

A的最左端 - B的最左端的值

A的最右端 - B的最左端的值

A的最左端 - B的最右端的值

A的最右端 - B的最左端的值

比较这四个值取最大的然后用双指针维护一下就可以了。

首先,为什么要排序:是为了帮助我们更好的去寻找这个剩余的数组中相差最大的值是多少。

其次,为什么要去找剩余数组中相差最大的值(事实表明,贪心的结论严格证明起来其实是非常困难的,这里我凭借感觉了):我们假设我们不选择相差最大的a 和 b,我们原本可以得到val = |a - b|,但是现在存在c使得|a - c| < |a - b|,我们如果选择c,那么剩下的n - 1的最优方案如果不选则b,那么我们一定可以选择b,所以b更加优秀。如果剩下的n - 1最优方案选择了b,也就是说有一个字母d选择了b

 1.a < b

   (1) a < c < d < b 那么我们按照策略获得val = b - a + d - c,val' = c - a + b - d。显然b + d > c + d, a + c < a + d, 所以val > val'

   (2) a < d < c < b, val = b - a + c - d, val' = c - a + b - d, val = val'

2.a > b(省略)

Ca的思路并不是很严谨(是在乱搞),所以仅仅提供一种思维方式 Qwq)

标签:Different,val,Very,端的,选择,1921,数组,左端
From: https://www.cnblogs.com/ybC202444/p/17985959

相关文章

  • CF-1921-F-根号分治
    1921-F题目大意有一个长为\(n\)的序列\(a\),有\(q\)次询问,对于每次询问:给定\(s,d,k\),请输出\(\sum_{i=1}^{k}i*a_{s+(i-1)*d}\)Solution根号分治。对于\(d\ge\sqrt{n}\)的情况,直接暴力计算即可。对于\(d\le\sqrt{n}\)的情况,这时需要预处理两个数组:\(pre,sum\),这里\(pr......
  • Feign源码解析6:如何集成discoveryClient获取服务列表
    背景我们上一篇介绍了feign调用的整体流程,在@FeignClient没有写死url的情况下,就会生成一个支持客户端负载均衡的LoadBalancerClient。这个LoadBalancerClient可以根据服务名,去获取服务对应的实例列表,然后再用一些客户端负载均衡算法,从这堆实例列表中选择一个实例,再进行http调用即......
  • CF1921 F Sum of Progression 题解
    QuestionCF1921FSumofProgression给定一个序列\(\{a\}\),有\(q\)组询问,对于每组询问\(s,d,k\),求\[a_s+a_{s+d}\cdot2+\cdots+a_{s+d(k-1)}\cdotk\]Solution\(s,d,k\)其实就是在描述一个等差数列考虑到\(d\timesk\len\)如果\(d\)很大,那么就意味着\(k\)很......
  • Codeforces Round 920 (Div. 3) D Very Different Array
    DVeryDifferentArray题意给出两个长度分别为\(n,m\)的数组\(a,c\),\(n<m\),从\(c\)中选择\(n\)个数并找到一个序列使得\(D=\sum_{i=1}^{n}|a_i-c_i|\)尽可能大,求D的值思路假设如果\(m\)和\(n\)一样大,那么找到这个序列的方法很简单:将两个序列分别排序后将其中一个转置,......
  • CF1921F Sum of Progression
    题目链接:CF一道经典的类型题,把这种类型的题拿出来单独说一下。注意到问题中涉及到需要维护\(a_{x+k\timesstep}\)这样的信息,这样的信息很难用树型结构维护,比较容易用块级结构维护,我们注意到其实是每次这种步长\(+step\)的信息很难维护,我们考虑一类特殊的分块:如果\(step\)......
  • 差分符号熵Differential symbolic Entropy,多尺度差分符号熵,层次差分符号熵,时移多尺度
    差分符号熵DifferentialsymbolicEntropy,多尺度差分符号熵,层次差分符号熵,时移多尺度差分符号熵,复合多尺度差分符号熵,精细复合多尺度差分符号熵(Matlab代码获取链接:https://mbd.pub/o/bread/mbd-ZZmblZlv)熵或复杂性度量区分时间序列类别和理解潜在动态的能力是众所周知的。该算法......
  • different python version + venv
    ubuntu系统上安装不同python版本https://www.bandwagonhost.net/7309.html比如安装Python3.7:sudoaptinstallpython3.7或者安装Python3.6:sudoaptinstallpython3.6安装之后,我们就可以使用Python对应版本了,比如看一下Python3.7的具体版本:python3.7-V构造应......
  • AI赋能建筑设计 | VERYCLOUD睿鸿股份与亚马逊云科技协力为AIRI lab. 打造生成式AI应用
    近年来,很多研究都致力于探索如何让建筑师借助人工智能的力量来促进并简化设计流程。生成式AI全球爆火以来,建筑设计领域也掀起了一场全新的思维变革。AI为建筑设计带来更多可能作为一家面向全球提供设计服务的企业,AIRIlab.计划推出一种可以根据文字生成效果图的服务,为建筑设计师提......
  • Understanding q-value and FDR in Differential Expression Analysis
     Understandingq-valueandFDRinDifferentialExpressionAnalysisDaqianIntroductiontoq-valueandFDRIndifferentialgeneexpressionanalysis,researchersareoftenconfrontedwiththechallengeofdistinguishingtruesignals—thosegenesthat......
  • 用RWEverything刷内存spd
    最近参与的一个项目,由于主板只支撑ddr3L的内存,需要把ddr3标压内存刷为ddr3L。通过百度找到如下:不无折腾篇五:DDR3标压内存改DDR3L低压条保姆级傻瓜教程于是动手实践了一下,特此记录本过程:1、找台支持ddr3标压的机子作为刷机平台,并下载好软件RWEverything1.72、寻找能刷spd的内......