Dang_Quan_10_Tin

CAU4_14

Mar 13th, 2022 (edited)
360
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.18 KB | None | 0 0
  1. #define task "CAU4_14"
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. using ll = long long;
  9. using ld = long double;
  10.  
  11. constexpr int N = 1e3 + 5;
  12. constexpr int Inf = 1e9 + 7;
  13.  
  14. int n, k, a[N], m, b[N];
  15.  
  16. void Read()
  17. {
  18.     cin >> n >> k;
  19.  
  20.     for (int i = 1; i <= n; ++i)
  21.         cin >> a[i];
  22. }
  23.  
  24. void Solve()
  25. {
  26.     for (int i = 1; i <= n; ++i)
  27.         if (i != k)
  28.             b[++m] = a[i];
  29.  
  30.     int ans(Inf);
  31.  
  32.     sort(b + 1, b + m + 1);
  33.  
  34.     if (n == 1)
  35.         ans = 0;
  36.     else if (k == 1 || k == n)
  37.         ans = min(abs(a[k] - b[m]), abs(a[k] - b[1])) + abs(b[m] - b[1]);
  38.     else if (k == 2 || k == n - 1)
  39.     {
  40.         if (n == 3)
  41.             ans = abs(a[k] - b[1]) + abs(a[k] - b[m]);
  42.         else
  43.         {
  44.             // 1-k-(2, m) or (2, m)-k-1
  45.             ans = min(ans, (b[m] - b[2]) + abs(b[1] - a[k]) + min(abs(b[m] - a[k]), abs(b[2] - a[k])));
  46.  
  47.             // m-k-(1,m-1) or (1, m-1)-k-m
  48.             ans = min(ans, (b[m - 1] - b[1]) + abs(b[m] - a[k]) + min(abs(b[1] - a[k]), abs(b[m - 1] - a[k])));
  49.  
  50.             // i-k-(1, m) or (1, m)-k-i
  51.             for (int i = 2; i < m; ++i)
  52.                 ans = min(ans, abs(b[i] - a[k]) + (b[m] - b[1]) + min(abs(b[m] - a[k]), abs(b[1] - a[k])));
  53.         }
  54.     }
  55.     else
  56.     {
  57.         for (int i = 2; i < m; ++i)
  58.             for (int j = i + 1; j < m; ++j)
  59.             {
  60.                 // (1, m)-k-(i,j) or (i,j)-k-(1,m)
  61.                 if (j - i + 1 >= n - k || j - i + 1 >= k - 1)
  62.                     ans = min(ans, (b[m] - b[1]) + (b[j] - b[i]) + min(abs(b[m] - a[k]), abs(b[1] - a[k])) + min(abs(b[i] - a[k]), abs(b[j] - a[k])));
  63.  
  64.                 // (1, i)-k-(j,m) or (j, m)-k-(1,i)
  65.                 if (j == i + 1 && (i == k - 1 || i == n - k))
  66.                     ans = min(ans, (b[i] - b[1]) + (b[m] - b[j]) + min(abs(b[1] - a[k]), abs(b[i] - a[k])) + min(abs(b[j] - a[k]), abs(b[m] - a[k])));
  67.             }
  68.     }
  69.  
  70.     cout << ans;
  71. }
  72.  
  73. int32_t main()
  74. {
  75.     ios_base::sync_with_stdio(0);
  76.     cin.tie(0);
  77.     cout.tie(0);
  78.  
  79.     if (fopen(task ".INP", "r"))
  80.     {
  81.         freopen(task ".INP", "r", stdin);
  82.         freopen(task ".OUT", "w", stdout);
  83.     }
  84.  
  85.     Read();
  86.     Solve();
  87. }
Add Comment
Please, Sign In to add comment