首页 > 其他分享 >Equalize

Equalize

时间:2024-02-20 16:00:01浏览次数:17  
标签:这个 构造方法 题解 数能 官方 Equalize

这道题目的官方题解讲的就很好

但是这个构造方法确实比较好,我当时想到了排序+去重,但是最后判断的时候利用了贪心,对任何一个剩下的元素\(a\),最后如果他要参与贡献的话,这个众数必须是\([a+1,a+n]\)中的一个数,而由于\(a\)从小到大排了序的,我们依次考虑的话,显然是每个\(a\)都选择\(a+n\)这个数,然后看看这个数能覆盖多少个数是最好的,然后实现用了二分

提一句,官方题解用的双指针

标签:这个,构造方法,题解,数能,官方,Equalize
From: https://www.cnblogs.com/dingxingdi/p/18023276

相关文章

  • Codeforces Round 924 (Div. 2)B. Equalize(思维+双指针)
    目录题面链接题意题解代码题面链接B.Equalize题意给一个数组\(a\),然后让你给这个数组加上一个排列,求出现最多的次数题解赛时没过不应该。最开始很容易想到要去重,因为重复的元素对于答案是没有贡献的。去重后排序。,然后维护一个极差小于n-1的区间,,区间长度就是可能的答案......
  • Educational Codeforces Round 159 (Rated for Div. 2) C. Insert and Equalize (贪心+
    EducationalCodeforcesRound159(RatedforDiv.2)C.InsertandEqualize思路:首先对\(a\)进行排序,然后对所有差值取gcd,获得可用的最大因子\(gc\),答案有两种情况:一种是\(a_{n+1}\)在$a_1\(~\)a_n$范围内,这时要获得最大的位置一种情况是$a_1\(~\)a_n$......
  • C. Insert and Equalize
    原题链接导论1.数列末尾插入一个没有在数列中出现过的数,然后对数列中的每个数加上x的若干倍数(其中的x对于每个数而言均相同),使得数列中的所有数均相等2.由导论1可以推出,x一定是\(|a[i]-a[j]|(1\leqi,j\leqn)\)的最大公约数3.导论2的时间复杂度显然太高了,因此猜想\(gcd(|a[i......
  • CF1902 C Insert and Equalize 题解
    LinkCF1902CInsertandEqualizeQuestion有一个\(n\)个元素的数组\(a\),每个元素都不一样现在我们需要在\(a\)中添加一个数字\(a_{n+1}\),和之前的元素都不一样然后选择一个数\(x\),可以在一个元素上加\(x\),为操作一次,(每次加的数都是\(x\))求,操作的最少次数Solution......
  • [Codeforces] CF1799B Equalize by Divide
    序列操作(divide.cpp)—CF1799B—1200题目描述给您一个\(a_1,a_2,\dotsa_n\)这样的正整数数组,您可以对它进行多次(可以是零次)这样的操作:选择两个索引\(i,j(1\leqi,j\leqn,i\neqj)\);将\(a_i\)赋值为\(\lceil\frac{a_i}{a_j}\rceil\)。这里的\(\lceilx\rceil\)......
  • CF1862G The Great Equalizer
    题目链接先不考虑修改操作。直接模拟题目意思,可以发现最后留下的一定是最小的数字(因为相同的数每次会保留第一个)。我当时是顺着这个思路做的题目,现在想想反过来想好像会让问题变得更简单,即认为每次保留最后一个相同的数字。那么现在每次留下的就是最后一个数字,显然每次操作会让......
  • G. The Great Equalizer
    G.TheGreatEqualizer通过分析之后得知,每次询问的答案就是当前数组中的最大值和当下数组排序后相邻元素差值的最大值之和。接下来考虑如何维护数组。这会想到用一颗二叉平衡搜索树来实现。这样的一颗树在STL里已经用multiset封装好了,直接使用即可。创建两个辅助函数add(intx......
  • CF1862G The Great Equalizer
    思路对于一个数组,每次操作会缩短排序后的数组的相邻两个数的差距,所以总共会执行\(k\)次操作,其中,\(k\)为排序后的数组的相邻两个数的最大差距。因为每次操作都会对最大数加\(1\),所以答案就是\(\text{数组中的最大数}+\text{排序后的数组的相邻两个数的最大差距}\)。因为......
  • G. The Great Equalizer
    G.TheGreatEqualizerTemaboughtanolddevicewithasmallscreenandaworn-outinscription"TheGreatEqualizer"ontheside.Thesellersaidthatthedeviceneedstobegivenanarray$a$ofintegersasinput,afterwhich"TheGreatE......
  • CF1799B Equalize by Divide题解
    本蒟蒻学习了jiangly大佬的思想,来发一个题解。大致题意:给定一个\(n\)个元素的数组\(a\),每次可以选择\(a[i]\)和\(a[j]\),然后使\(a[i]=\lceil\frac{a_i}{a_j}\rceil\),如果最后可以使数组中的所有元素都相等,那么输出Yes,并输出每一个操作\(i,j\);否则输出No。本人不......