中位数+暴力——cf433C

深碍√TFBOYSˉ_ 2023-10-12 08:22 21阅读 0赞

/* 中位数到所有数的距离之和最小 因为只能改一个数，所以我们找一个数，将其改为和其相邻的数的中位数，使答案最小 先求一次原答案 把每个数相邻的数用vector存下来，然后排序找中位数，计算减小的量 
    */
    #include<bits/stdc++.h>
    #include<vector> 
    using namespace std;
    #define ll long long
    #define N 200005
    vector<int> v[N];
    int n,m,a[N];
    
    int main(){
        cin>>n>>m;
        for(int i=1;i<=m;i++)cin>>a[i];
        long long sum=0;
        for(int i=1;i<m;i++) 
            sum+=abs(a[i]-a[i+1]);
        /*if(a[1]!=a[2]){
            v[a[1]].push_back(a[2]);
            v[a[2]].push_back(a[1]);
        }*/
        for(int i=1;i<m;i++)if(a[i]!=a[i+1]){
            v[a[i]].push_back(a[i+1]);
            v[a[i+1]].push_back(a[i]);
        }
        
        for(int i=1;i<=200000;i++)sort(v[i].begin(),v[i].end());
        ll ans=sum;
        for(int i=1;i<=200000;i++)if(v[i].size()){
            ll last=0;
            for(int j=0;j<v[i].size();j++)
                last+=abs(i-v[i][j]);
            ll now=0,tmp=v[i].size()/2;
            for(int j=0;j<v[i].size();j++)
                now+=abs(v[i][tmp]-v[i][j]);
            ans=min(ans,sum-last+now);
        }
        cout<<ans<<'\n';
    }

转载于:https://www.cnblogs.com/zsben991126/p/11444352.html

发表评论取消回复

表情：

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

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

相关阅读

相关【sorting+暴力】CF624div3 C. Perform the Combo

[Problem - C - Codeforces][] 题意：给定一个字符串s和一个数列a，遍历数列a，每次操作都会给字符串前缀的前ai个的元素出现次数++，问你所有操

ゝ一世哀愁。/ 2024年03月22日 14:21/ 0 赞/ 72 阅读

相关【*2000 暴力树形DP】CF1230 E

[Problem - E - Codeforces][] 题意： ![25adb30bd05a42c1b4173f8e1deb9f20.png][] 思路： ![29a

深藏阁楼爱情的钟/ 2024年03月17日 18:39/ 0 赞/ 103 阅读

相关【暴力DP】CF1409 F

[Problem - F - Codeforces][] 题意： ![0b383875a1444f75b1163b33ac695a0b.png][] ![e01ceb20

骑猪看日落/ 2024年03月01日 07:49/ 0 赞/ 51 阅读

相关【暴力剪枝】CF1708D

[https://codeforces.com/contest/1708/problem/D][https_codeforces.com_contest_1708_proble

柔光的暖阳◎/ 2024年02月21日 10:23/ 0 赞/ 47 阅读

相关中位数+暴力——cf433C

/ 中位数到所有数的距离之和最小因为只能改一个数，所以我们找一个数，将其改为和其相邻的数的中位数，使答案最小先求一次原答案把每个数相邻的数用vector存下来，然

深碍√TFBOYSˉ_/ 2023年10月12日 08:22/ 0 赞/ 22 阅读

相关暴力——cf557c

//枚举高度[1,100000]，>l的全部割掉，<l的砍掉最小的 include<bits/stdc++.h> using namespace std

╰半橙微兮°/ 2023年10月12日 08:19/ 0 赞/ 21 阅读

相关暴力——cf1202C

直接去考虑细节很多，不如暴力做即在四个方向到达最远前向反方向走一步，答案肯定是从这四种情况+不多走里出的 include<bits/stdc++.h> u

谁借莪１个温暖的怀抱￠/ 2023年10月11日 09:09/ 0 赞/ 15 阅读

相关 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 赞/ 118 阅读

相关 #433 - C. Planning（贪心，优先队列）

-------------------- 题目连接：[http://codeforces.com/contest/854/problem/C][http_codeforces

落日映苍穹つ/ 2022年06月08日 05:20/ 0 赞/ 204 阅读

相关 [CF.Skills]在.NET CF中嵌入Media Player(C#)

昨天有人在[http://winbile.net/bbs][http_winbile.net_bbs]上问到，在WM5上面如何使用MediaPlayer播放音乐。其实微软

痛定思痛。/ 2022年03月29日 04:39/ 0 赞/ 238 阅读