fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  4. #define endl "\n"
  5. #define f(i, n) for(int i = 0; i < n; ++i)
  6. #define pb push_back
  7. #define eb emplace_back
  8. #define m_p make_pair
  9. #define T int t = 0; cin >> t; while(t--)
  10. #define pr(a) for(int i = 0; i < (int)a.size(); ++i)cout << a[i] << " ";cout << endl;
  11. #define b_e(a) a.begin(), a.end()
  12. typedef long long ll;
  13. typedef long double lld;
  14. const ll mod = 1e9 + 7;
  15.  
  16. const ll mx = 2e6 + 2;
  17. const ll inf = 2e18;
  18. const int sz = 256;
  19. const int max_k = 20;
  20. const int len = 2e5 + 2;
  21. typedef long long ll;
  22.  
  23. void solve(){
  24.     int w, n;
  25.     cin >> w >> n;
  26.     vector<ll>a(2 * w);
  27.     f(i, w)cin >> a[i];
  28.     sort(a.begin(), a.begin() + w);
  29.     for(int i = w; i < 2 * w ; ++i)a[i] = a[i - w] + n;
  30.     vector<ll>pref(2 * w);
  31.     pref[0] = a[0];
  32.     for(int i = 1; i < 2 * w; ++i)pref[i] = pref[i - 1] + a[i];
  33.     auto get_sum = [&](int i , int j){
  34.         return pref[j] - (i > 0 ? pref[i - 1] : 0);
  35.     };
  36.     auto get = [&](int i){
  37.         int j = i + w - 1;
  38.         int k = a[(i + j) >> 1];
  39.         ll sum_left = get_sum(i, (i + j) >> 1);
  40.         ll sum_right = get_sum((i + j) >> 1 , j);
  41.         ll l = ((i + j) >> 1) - i + 1;
  42.         ll r = j - ((i + j) >> 1) + 1;
  43.         //cout << i << " " << l << " " << r << " " << sum_left << " " << sum_right << " " << k << endl;
  44.         return l * k - sum_left + sum_right - r * k;
  45.     };
  46.     ll ans = inf;
  47.     for(int i = 0; i < w; ++i){
  48.         ans = min(ans, get(i));
  49.     }
  50.  
  51.     cout << ans << endl;
  52.  
  53.  
  54. }
  55. void input(){
  56.     IOS;
  57.     int tt;
  58.     cin >> tt;
  59.     for(int cas = 1; cas <= tt; ++cas){
  60.         cout << "Case #" << cas << ": ";
  61.         solve();
  62.     }
  63. }
  64.  
  65. int main(){
  66.     input();
  67.     return 0;
  68. } 
  69. /*
  70. freopen("input.txt","r",stdin);
  71. freopen("output.txt","w",stdout);
  72. */
  73.  
Success #stdin #stdout 0s 4176KB
comments (?)
stdin
copy 
2
3 5
2 3 4
4 10
2 9 3 8
stdout
copy 
Case #1: 2
Case #2: 8
https://ideone.com/NZJ4YA
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!