CF433C Ryouko's Memory Note（贪心）题解

题意

给出2个正整数 (n,m(1leq n,m leq 10^5))与长度为(m)的序列(a[1-m])，保证(a[i]leq n)，你可以把所有值为(a[i])的元素改为(a[j])，可以不改且只能改一次，要求最小化(sumlimits_{i=1}^{ileq m-1} |a_i-a_{i+1}|)。

算法

贪心，暴力枚举

思路

首先要知道一个结论：

当(a)为序列(b)的中位数时，(sumlimits_{i=1}^{ileq n}{|a-b_i|})最小。

放到这个题目里，对于每一个元素(a[i])，序列(b)就是与它相邻且不相等的元素集合。所以，我们可以统计出与每一个相邻的数，排序之后用中位数计算对答案的贡献。

由于每一个数最多被枚举了2遍，所以总复杂度为(O(2mlogm))。

具体实现请看代码。

参考代码

#include <cstdio>
#include <algorithm>
#include <vector>
#define LL long long

using namespace std;

const int maxn = 1e5 + 10;
int n,a[maxn],m;
LL Ans = 0;
vector<int> v[maxn];

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++ i) scanf("%d", a + i);
    for(int i = 1; i <= m; ++ i){
        if(a[i] != a[i - 1] && i != 1) v[a[i]].push_back(a[i - 1]);
        if(a[i] != a[i + 1] && i != m) v[a[i]].push_back(a[i + 1]);
        if(i != 1) Ans += abs(a[i] - a[i - 1]);  //先处理出初始答案
    }
    LL ls = Ans;
    for(int i = 1; i <= n; ++ i){
        int len = v[i].size();
        if(!len) continue;
        sort(v[i].begin(), v[i].end());
        int pos = v[i][len / 2]; LL ret = ls;
        for(int j = 0; j < len; ++ j){
            ret -= abs(i - v[i][j]);
            ret += abs(pos - v[i][j]); //计算更改后的答案
        }
        Ans = min(Ans, ret);
    }
    printf("%lld
", Ans);
    return 0;
}