D1. Equalizing by Division（hard 1600）————暴力+贪心

ゞ浴缸里的玫瑰 2024-04-18 14:06 38阅读 0赞

[题目连接][Link 1]

/***** 该题是用最少的操作， 产生k个相等的数字 思路： 直接暴力， 因为每个数大小2e5 ， 2的18次方2e5多， 所以每个数最多除18次 2e5个数，在2秒内是可以的。 ******/
    #include <iostream>
    #include<cstdio>
    #include<algorithm>
    #define ll long long
    using namespace std;
    const int maxn = 2e5+50;
    ll cnt[maxn];//统计该数的数量（来判断是否能达到k个）
    ll tim[maxn];//统计该数达到k个至少需要几次操作
    ll a[maxn];
    const ll inf = 0x3f3f3f3f3f3f;
    int main()
    { 
       
        ios_base::sync_with_stdio(false);
        ll n, k;
        cin>>n>>k;
    
        for(ll i = 0;i < n;i++)
        { 
    
            cin>>a[i];
    
        }
        sort(a, a+n);// 从小达大排下序
        for(ll i= 0;i <n;i++)
        { 
            cnt[a[i]]++;
             ll sum = 0;
            while(a[i])
            { 
    
                sum++;
                if(cnt[a[i]/2]< k)// 如果该数不倒k个
                { 
                    cnt[a[i]/2]++;
                    tim[a[i]/2] += sum;
                }
                a[i]/=2;
    
            }
        }
        ll Min = inf;
        for(ll i = 0;i <maxn;i++)
        { 
            if(cnt[i]>= k && tim[i] < Min)
            { 
                Min = tim[i];
            }
        }
        cout<<Min<<endl;
        return 0;
    }

[Link 1]: http://codeforces.com/problemset/problem/1213/D2

发表评论取消回复

表情：

评论列表（有 0 条评论，38人围观）

还没有评论，来说两句吧...

相关阅读

相关 D1. Equalizing by Division（hard 1600）————暴力+贪心

题目连接][Link 1] /***** 该题是用最少的操作，产生k个相等的数字思路：直接暴力，因为每个数大小2e5 ， 2的18次方2e5多，所以每...

ゞ浴缸里的玫瑰/ 2024年04月18日 14:06/ 0 赞/ 39 阅读

相关 [Gym-101550D] 贪心

道题贪心题，硬生生的让我做成了dp 思路：低价买高价卖找非递减子序列（就是将该段序列看成多个非递减子序列的拼接） include<b...

﹏ヽ暗。殇╰゛Y/ 2024年04月17日 23:44/ 0 赞/ 76 阅读

相关【贪心】CF1841 D

[Codeforces][] 题意： ![f231a62f84944973acc878c8bcd43a09.png][] ![eed5aa21f67e4bf8a27aad

绝地灬酷狼/ 2024年03月23日 23:24/ 0 赞/ 55 阅读

相关【贪心】CF1779 D

不会1700 [Problem - 1779D - Codeforces][] 题意： ![2812e830d8fc42acaa190aa13f186e7a.png][]

r囧r小猫/ 2024年03月23日 23:20/ 0 赞/ 87 阅读

相关 C. The Number Of Good Substrings————暴力思维（1600 cf）

[https://codeforces.com/problemset/problem/1217/C][https_codeforces.com_problemset_probl

短命女/ 2023年08月17日 16:21/ 0 赞/ 106 阅读

相关 codeforces 276D 贪心

D. Little Girl and Maximum XOR time limit per test 2 seconds memory limit per test 2

妖狐艹你老母/ 2022年07月24日 06:26/ 0 赞/ 165 阅读

相关 CodeForces 825D(贪心)

问题描述: You are given two strings s and t consisting of small Latin letters, string s can

ゝ一纸荒年。/ 2022年06月06日 14:16/ 0 赞/ 136 阅读

相关 C. Prime Swaps（暴力+贪心）

题目链接：[http://codeforces.com/problemset/problem/432/C][http_codeforces.com_problemset_pro

亦凉/ 2021年11月05日 13:00/ 0 赞/ 244 阅读

相关 D. Pythagorean Triples (math、暴力)

[题目][Link 1] 题解： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aH

梦里梦外;/ 2021年07月17日 00:30/ 0 赞/ 287 阅读

相关 1421D - Hexagons (贪心)

[题目][Link 1] 思路：将此坐标转化为直角坐标系（纵坐标，横坐标），然后将六条路径优化，上cs = min(c6, c5 + c1), 下cx = min(c3,

清疚/ 2021年07月16日 18:45/ 0 赞/ 287 阅读