首页 > 其他分享 >CF387B George and Round 题解

CF387B George and Round 题解

时间:2024-03-09 12:37:47浏览次数:27  
标签:题解 CF387B Round ans gets George 指针

考虑采用双指针法解决此题。

首先需要对 \(a,b\) 数组排序,并且维护两个指针 \(l,r\),分别指向 \(a,b\) 两个数组中的元素。

接着循环移动 \(r\) 指针,每次都尝试匹配 \(a_l\) 和 \(b_r\):

  • 若 \(a_l \le b_r\),则说明 \(a_l = b_r\) 或可以采用减少 \(b_r\) 的方式使 \(a_l = b_r\),这时我们就称 \(a_l\) 和 \(b_r\) 匹配成功。接着令不需要添加的元素个数 \(ans \gets ans+1\),同时也令 \(l \gets l+1\)(右移一位)。

  • 否则,则说明需要添加一个元素,不进行任何操作。

当 \(l,r\) 指针移动到末尾时循环结束,此时的答案即为 \(n-ans\)。

代码非常好写,因此不贴了。

标签:题解,CF387B,Round,ans,gets,George,指针
From: https://www.cnblogs.com/XOF-0-0/p/18062506

相关文章

  • P3670 [USACO17OPEN] Bovine Genomics S 题解
    题意给定\(2\)组字符串,每组\(n\)个,每个字符串包含\(m\)个字符。我们称一个三元组\((i,j,k)\)是合法的,当且仅当第二组的每个字符串中下标为\((i,j,k)\)的字符拼成的字符串与第一组的每个字符串中下标为\((i,j,k)\)的字符拼成的字符串均不相等。现在需要你对于给定的......
  • CF99B Help Chef Gerasim 题解
    分别对三种情况进行分类讨论。第一种情况:显然,若\(\sum^{n}_{i=1}a_i\bmodn\neq0\),则输出\(\texttt{Unrecoverableconfiguration.}\);同时,我们遍历\(a_{1\simn}\),若存在两个以上的\(a_i\)满足\(a_i\neq\sum^{n}_{i=1}a_i\divn\),则也输出\(\texttt{Unreco......
  • P10217 [省选联考 2024] 季风题解
    考场上没写出来,火大,实际上这题放校内%你赛我肯定写的出来,可惜这是省选。实际上这题不难,主要是观察性质,接着拆柿子,然后就是有点难写,要写得好看有点考验代码构建能力和数学能力。我们考虑原题的每对\((x,y)\)都要满足\(|x|+|y|\lek\)而我们可以知道后面应该填的\((x,y)\)如......
  • CF348A Mafia 题解
    由于题目具有十分明显的单调性(若\(x\)局能满足要求,则\(>x\)局一定能满足;若\(x\)局无法满足要求,则\(<x\)局也无法满足),因此我们考虑进行二分答案。二分所需要的局数\(x\),设所有人想玩的总局数为\(S\),由题意可得\(S=\sum^{n}_{i=1}a_i\)。因为每局都会有\(1\)人主持,\(n......
  • [ABC297F] Minimum Bounding Box 2 题解
    容斥真有趣。有一个性质:两个相同的子矩阵,对答案的贡献一定相同。所以就只需要枚举矩阵大小即可。我们设当前矩阵长\(i\)宽\(j\)(对应的,\(H\)为长,\(W\)为宽),假如要给答案做出贡献,矩阵的四条边一定都有点,发现可以容斥了。至少\(0\)条边上有点的方案数为\(a=C_{i\times......
  • P4139 上帝与集合的正确用法 题解
    传送门我觉得这题最有意思的其实是"最终会固定为一个数"这个结论。扩展欧拉定理:\(a^b\bmodp\),当\(b\ge\varphi(p)\)时,\(a^b\equiva^{b\bmod\varphi(p)+\varphi(p)}\pmodp\)。所以\(2^{2^{2^{\cdots}}}\)可以递归求解。边界条件\(p=1\)。复杂度如何保证?其实就是......
  • P4774 屠龙勇士 题解
    传送门显然每一只龙对应了唯一的一把剑。用multiset可以求出每一把剑。于是题目就变成了:\[\begin{cases}b_1x\equiva_1\pmod{m_1}\\b_2x\equiva_2\pmod{m_2}\\\dots\\b_nx\equiva_n\pmod{m_n}\end{cases}\]如果\(b_i=1\),直接EXCRT即可。现在\(b_i>1\),还是以EXCRT......
  • Codeforces Round 656 (Div. 3) F. Removing Leaves
    ProblemDescription给出一棵\(n\)个节点的无根树。你可以进行以下操作:选择\(k\)个共同父节点的叶子节点,将\(k\)个节点和与父节点相连的边删去。求最大操作次数。Input第一行输入一个整数\(t\)\((1\let\le2\times10^4)\),表示测试组数。接下来每组测试数据第......
  • APatch常见问题解答
    常见问题解答什么是APatch?APatch是一种类似于Magisk或KernelSU的root解决方案,但APatch提供更多功能。APatch分别结合了Magisk方便易用的通过boot.img安装的方法,和KernelSU强大的内核修补能力。APatch与Magisk的区别?Magisk对启动映像中的ramdisk进行补丁,以修改init系统。而AP......
  • P6810 「MCOI-02」Convex Hull 凸包 题解
    分析推式子题。\[ans=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\tau(i)\tau(j)\tau(\gcd(i,j))\]对于\((i,j)\),若\(k\)是\((i,j)\)的因子,则\(k\)一定整除\(i,j\),所以有:\[\\\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\tau(i)\tau(j)\sum\limits......