Codeforces Round #248 (Div. 2) C. Ryouko's Memory Note （vector 替换）

时间：2023-03-08 16:34:27

题目链接

题意：给m个数字， 这些数字都不大于 n,  sum的值为相邻两个数字 差的绝对值。求这n个数字里把一个数字 用 其中另一个数字代替以后，

最小的sum值。

分析：刚开始以为两个for 最坏情况下 会超时，但是实际不会，因为如果第一个for循环多的话，第二个for循环肯定少。

替换的时候，用这个数相关联的排序后 中间的一个数替换，是最小的。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <vector>

 #include <algorithm>

 using namespace std;

 #define Min(a,b)((a)>(b)?(b):(a))

 const int maxn =  + ;

 int a[maxn];

 vector<int>v[maxn];

 int main()

 {

     int n, m, i, j, _size, tmp;

     __int64 sum, sum2, sum3;

     scanf("%d%d", &n, &m);

     sum = ;

     for(i = ; i < m; i++)

     {

         scanf("%d", &a[i]);

         if(i !=  && a[i] != a[i-])

         {

             v[a[i]].push_back(a[i-]);

             v[a[i-]].push_back(a[i]);

             sum += abs(a[i] - a[i-]);

         }

     }

     vector<int>x;

     sum3 = sum;

     for(i = ; i <= n; i++)

     {

         _size = v[i].size();

         if(_size == )

             continue;

         x = v[i];

         sort(x.begin(), x.end());

         tmp = x[_size/];

         sum2 = sum3;

         for(j = ; j < _size; j++)

             sum2 += (abs(tmp-x[j]) - abs(i-x[j]));

         sum = Min(sum, sum2);

     }

     printf("%I64d\n", sum);

     return ;

 }

相关文章