首页 > 其他分享 >Educational Codeforces Round 159 (Rated for Div. 2) C. Insert and Equalize (贪心+数论)

Educational Codeforces Round 159 (Rated for Div. 2) C. Insert and Equalize (贪心+数论)

时间:2023-12-16 21:35:16浏览次数:36  
标签:Insert Educational Rated int long gc define

Educational Codeforces Round 159 (Rated for Div. 2) C. Insert and Equalize

思路:

首先对 \(a\) 进行排序, 然后对所有差值取gcd ,获得可用的最大因子 \(gc\),

答案有两种情况:

  • 一种是 \(a_{n+1}\) 在 $a_1 \(~\) a_n$ 范围内,这时要获得最大的位置

  • 一种情况是 $a_1 \(~\) a_n$ 范围内 对 \(gc\) 无空可插入,因此 \(a_{n+1}\) = \(a_n + gc\)

对两种情况:

  • 第一种所有数用 \(gc\) 加到 \(a_n\)
  • 第二种 所有数用 \(gc\) 加到 \(a_{n+1}\)
#define int long long
#define LL long long
#define ld long double
#define fr(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
#define ppb pop_back()
#define pb push_back
#define pf push_front
#define so(a) sort(a.begin(),a.end())
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define ikun ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0)
//mp.reserve(1024);
//mp.max_load_factor(0.25);

using namespace std;

const int N = 1e5 + 10;

vector<int>a;

int gcd(int a, int b)
{
    if (b)return gcd(b, a % b);
    return a;
}

void solve()
{
    a.clear();
    int n;
    cin >> n;
    int x;
    fr(i, 1, n)
    {
        cin >> x;
        a.pb(x);
    }

    so(a);
    if (a[0] == a[n - 1])
    {
        cout << 1 << endl;
        return;
    }

    int gc = a[n - 1] - a[0];
    fr(i, 1, n - 1)
    {
        if (a[i] != a[i - 1])
        {
            gc = gcd(gc, a[i] - a[i - 1]);
        }
    }

    int ans = 0;
    int p = a[n - 1] + gc;
    fr(i, 0, n - 1)
    {
        ans += ( p - a[i]) / gc;
    }

    p = a[n - 1];
    rf(i,n - 1,0)
    {
        if (p == a[i])
        {
            p -= gc;
        }
        else
            break;
    }

    int res = (a[n - 1] - p) / gc;
    fr(i,0,n - 1)
    {
        res += (a[n - 1] - a[i]) / gc;
    }

    cout << min(ans, res) << "\n";
}

signed main()
{
    ikun;
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

标签:Insert,Educational,Rated,int,long,gc,define
From: https://www.cnblogs.com/ikunhuaji/p/17908401.html

相关文章

  • kettle更新组件(insert_update)
    2种装载方式:全量装载和增量装载插入更新与表到表区别:表到表:只追加数据,不管表里重不重复插入更新:对比关键字段,更新所有数据(不会删除)创建数据流:需求:表输入组件只是将数据追加装载到表中,并不是我们想要的更新数据:如下:插入/更新匹配关键字id=id保留关键字的字段,用来匹......
  • insert语句详解
    --insert插入语句(添加)--语法insertinto表名([字段名1,字段名2,字段名3])values('值1(字段名123)'),('值2(字段名123)'),('值3(字段名123)'),,,INSERTINTO`student2`(`name`)VALUES('焯');--由于主键自增我们可以省略(如果不写表的字段,他就会一一匹配)INSERTINTO`student2`(`name`)......
  • sqlalchemy 实现 mysql INSERT INTO...ON DUPLICATE KEY UPDATE语法
    1.前言myql的INSERTINTO...ONDUPLICATEKEYUPDATE语句,简单点来说,就是如果记录不存在,则插入,如果记录存在,则更新。那怎么判断记录存在否?——主键、唯一键。那不是可以使用replace语句吗?——原理上可以,但是sqlalchemyorm中的的实现,是使用merge语法,这个语法有一个限制,就是判......
  • VECTOR INSERT()
    #include<iostream>#include<vector>usingnamespacestd;intmain(){vector<int>a(20);a.push_back(1);intarr[]={1,2,3,4,5};vector<int>b(arr,arr+sizeof(arr)/sizeof(int));intar[]={7,8,9,10,11};vecto......
  • Educational Codeforces Round 158 (Rated for Div. 2)
    Preface补题,妈的现在EduE都做不来这搞毛啊A.LineTrip签到#include<cstdio>#include<iostream>#include<utility>#include<vector>#include<cstring>#include<cmath>#include<cstdlib>#include<algorithm>#include<queue&......
  • C. Insert and Equalize
    原题链接导论1.数列末尾插入一个没有在数列中出现过的数,然后对数列中的每个数加上x的若干倍数(其中的x对于每个数而言均相同),使得数列中的所有数均相等2.由导论1可以推出,x一定是\(|a[i]-a[j]|(1\leqi,j\leqn)\)的最大公约数3.导论2的时间复杂度显然太高了,因此猜想\(gcd(|a[i......
  • CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
    Preface补题,经典不会F,看了会题解发现看不懂,索性直接开摆A.JaggedSwaps判断\(a_1\)是否为\(1\)即可#include<cstdio>#include<iostream>#include<utility>#include<vector>#include<cstring>#include<cmath>#include<cstdlib>#include<al......
  • perl:mysql binlog iud (insert、update、delete)分析 小脚本:实用程序
    1#!/usr/bin/perl2#utf-834usestrict;5usePOSIX;6useTime::HiResqw/sleeptime/;78$|=1;910my$line='#-----------------------------------------------------------------------';11my$debug=0;1213##------------......
  • Educational Codeforces Round 159 总结
    最失败的一集。C开题顺序搞错,不小心先开了C,以为是A。还好C不难。题意大概是在给定的数组最后添一个数(所有数两两不同),再自定义一个数\(k\),数组中每个数可以加上若干个\(k\),最后使得所有数字相等。要求加\(k\)的次数最少。如果不加最后一个数,那么显然把所有的数加到与最大......
  • [CF1902] Educational Codeforces Round 159 A~E 题解
    [CF1902]EducationalCodeforcesRound159A~E题解A.BinaryImbalance很快观察到如果有不同的相邻元素,那么一定有解,意味着如果全是1无解,其他有解B.GettingPoints题面很长,可以发现,最好的偷懒方式一定是把所有的课都拖到最后几天上(真实),可以简单调整证明这样是不劣的,最后......