首页 > 编程语言 >CodeForces Dora and C++ (2007C) 题解

CodeForces Dora and C++ (2007C) 题解

时间:2024-11-01 21:08:49浏览次数:1  
标签:... gcd space int 题解 CodeForces Dora 数组 ans

CodeForces Dora and C++ (2007C) 题解

题意

给一个数组 \(c_{1...n}\),定义数组的 \(range\) 是最大值减最小值,即极差。给出两个值 \(a\) 和 \(b\),每步操作中,可给数组中任一一个数增大 \(a\) 或增大 \(b\)。问任意步操作后(可以是 \(0\) 步),极差的最小值。

思路

(要直接看答案可以跳过直接看『过程』)

先思考 \(a=b\) 的情况怎么做。我们总能经过不断选最小数使之加 \(a\) 的操作,使数组中的数极差小于 \(a\)。此时可枚举每一个数,即考虑每个 \(c_i(i=1,2,...,n)\),找到该 \(c_i\) 是最小值时,整个数组的情况(方法在后)。对种可能结果,我们取其中最小的,就是答案。

要使 \(c_i\) 是数组中的最小值,即要使所有小于它的数都加上 \(a\),此时我们首先发现:数组中任意数加上 \(a\) 后,都会比原先的最大值大,那么操作后的最大值必然在这些没加上 \(a\) 的值里出现。我们再发现:操作后的最大值,就是所有小于 \(c_i\) 的数中,最大的那个,即是找 \(c_j(j\in \{1, 2, ..., n\} ,\forall c_k \in \{c_k;c_k<c_i,k = 1, 2, ..., n\}),c_j\ge c_k\)。所以,只要找到这个次小于 \(c_i\) 的值 \(c_j\),就能找到这种情况的极差,极差为 \(c_j + a - c_i\),不妨排个序,这样每个结果就是 \(ans_i=\begin{cases}c_{i-1} + a - c_i, \space i>1\\c_n-c_1, \space i=1 \end{cases}\),再取 \(min_{i=1}^n\{ans_i\}\) 即是答案。

当 \(a\neq b\) 时,首先要发现我们可以等价地把某数等价地加或减 \(a\):如果要对某数减 \(a\),等价于给其他数都加上 \(a\);对 \(b\) 同理。再根据裴蜀定理,可知我们总是能对某数加或减 \(d(d=gcd(a,b))\),那么就转化成了第一种情况了。

过程

  1. 令 \(d=gcd(a,b)\),注意此处不同于题目定义的极差 \(d\)
  2. \(c_i \gets c_i \space mod \space d,\space i=1,2,...,n\)
  3. 输出 \(min_{i=1}^n\{ans_i\}\),其中 \(ans_i=\begin{cases}c_{i-1} + d - c_i, \space i>1\\c_n-c_1, \space i=1 \end{cases}\)

代码(C++)

#include <bits/stdc++.h>
#define chmin(a, b) if (a > (b)) a = (b)
using namespace std;

constexpr int N = 1e5 + 3;
int c[N];

int gcd(int a, int b) {
    while (b != 0) {
        int tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

void solve()
{
    int n, a, b;
    cin >> n >> a >> b;
    int d = gcd(a, b);
    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
        c[i] %= d;
    }
    sort(c + 1, c + 1 + n);
    int ans = c[n] - c[1];
    for (int i = 2; i <= n; ++i) chmin(ans, c[i - 1] + d - c[i]);
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

标签:...,gcd,space,int,题解,CodeForces,Dora,数组,ans
From: https://www.cnblogs.com/wongdzoendzi/p/18521281

相关文章

  • Codeforces Round 982 (Div. 2)解题报告
    CodeforcesRound982(Div.2)解题报告A显然答案不会小于\(2(\maxw+\maxh)\)。构造方案学习样例一,挺明显的。B有个小性质(好像没用):一旦能通过操作变成non-increasing,再对整个序列操作一次必然变为同一个数字。我们把一开始remove的数字记为A类,通过操作删掉的记为B类......
  • 第八届御网杯线下赛Pwn方向题解
    由于最近比赛有点多,而且赶上招新,导致原本应该及时总结的比赛搁置了,总结来说还是得多练,因为时间很短像这种线下赛,一般只有几个小时,所以思路一定要清晰,我还是经验太少了,导致比赛力不从心,先鸽了~Skillchecksec检查保护(没有开PIE和Canary)ida逆向分析一下不同的选项对应不同的功......
  • 【考试题解】多校A层冲刺NOIP2024模拟赛17
    A.网格(grid)题目内容给你一个\(n\timesm\)的字符网格\(s\),\(s_{i,j}\in[1,9]\cup\{+,*\}\),从\((1,1)\)开始,仅向下或向右走并最终到达\((n,m)\)的路径被称为合法路径,求所有合法路径对应的表达式的运算结果之和,答案对\(998244353\)取模。部分分44pts爆搜,枚举路径,......
  • 2024 -- 国庆集训 -- 临沂四中 -- 10月01 日 -- S/N模拟赛#1 题解
    A.2025--[炼石计划--NOIP模拟三]--T1--矩形赛时草了个\(O(n^4\log(n))\)竟然能过70分虽然本来就是这么分配的,发现正解只需将二分改为双指针就可以了,最气的是上面计算的时候用到还是尺取下面就用的二分(唐诗)。其实这题就是暴力,然后在低级的暴力上加一些操作变得稍微高级一......
  • abc318_g Typical Path Problem 题解 圆方树
    题目链接:https://atcoder.jp/contests/abc318/tasks/abc318_g题目大意:给出一个有\(n\)个顶点和\(m\)条边的无向连通图\(G\),没有重边和自环。顶点的编号为\(1\simn\),边的编号为\(1\simm\),第\(i\)条边连接顶点\(u_i\)和\(v_i\)。给出图上三个不同的顶点\(A,B,C......
  • Educational Codeforces Round 20 E. Roma and Poker
    差分约束我们记W表示\(1\),L表示\(-1\),D表示\(0\),然后记前\(i\)位的前缀和是\(dis[i]\)。则我们可以根据题面得到如下约束。当前位是W,则有\[\left\{\begin{matrix}dis[i]-dis[i-1]\le1\\dis[i-1]-dis[i]\le-1\end{matrix}\right.\]当前位是L,则有\[\left\{\begin{m......
  • 《上海市计算机学会竞赛平台2024年8月月赛丙组题目T1 统计得分 T2 等差数列的素性 T3
    T1统计得分内存限制: 256 Mb时间限制: 1000 ms题目描述在一场知识竞赛中,选手答对一题得 11 分,答错不得分且要倒扣 11 分,但扣分不能让分数小于 00。给定一个由 Y 及 N 构成的字符序列,答对记为 Y,答错记为 N。选手一开始从 00 分开始,请输出选手最后的得分......
  • 思维题配套题解
    配套题单:CodeForces思维题目CF79DPassword你有\(n\)个灯泡,一开始都未点亮。同时你有\(l\)个长度,分别为\(a_1\sima_l\)。每次你可以选择一段连续的子序列,且长度为某个\(a_i\),并将这些灯泡的明灭状态取反。求最少的操作次数,使得最后有且仅有\(k\)个位置是亮的,......
  • 题解 洛谷 Luogu P1308 [NOIP2011 普及组] 统计单词数 C++
    题目传送门:P1308[NOIP2011普及组]统计单词数-洛谷|计算机科学教育新生态https://www.luogu.com.cn/problem/P1308getline() 会清除使当次getline() 终止的换行,而cin 不会因此cin 以换行终止,之后还需要getline()的话,需要用getchar() 吞换行Linux的一些相......
  • 在包装网站pacdora充值的时候用了这个折扣码,会员价直接打折!比平时便宜多了
    只需要按照图片示意的步骤操作就行了!需要手动充值,自动续费是不享受折扣的,用折扣码充值完后记得关掉自动续费包月功能~pacdora会员折扣码:JYC20字母用大写!不要有空格键!每次充值时输入折扣码,充值好后记得关掉自动续费功能,折扣码只有手动有效! ......