fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define flow ios_base::sync_with_stdio(false);cin.tie(NULL);
  5. int main()
  6. {
  7.     flow;
  8.     ll t,l,r,mid;ll cur,target;cin>>t;
  9.     for(int query=1;query<=t;query++)
  10.     {
  11.         ll w;ll n;cin>>w>>n;ll ans=LONG_MAX;
  12.         ll a[w];
  13.         for(int i=0;i<w;i++)cin>>a[i];
  14.         sort(a,a+w);
  15.         ll pfx[w];
  16.         for(int i=0;i<w;i++)pfx[i]=0;
  17.         pfx[0]=a[0];
  18.         for(int i=1;i<w;i++)pfx[i]=pfx[i-1]+a[i];
  19.         for(int i=0;i<w;i++)
  20.         {
  21.             l=i+1;r=w-1;target=a[i];
  22.             while(l<=r)
  23.             {
  24.                 mid=(l+r)/2;
  25.                 cur=a[mid];
  26.                 if((cur-target)>=(n+target-cur))r=mid-1;
  27.                 else l=mid+1;
  28.             }
  29.             ll bb=(l-i-1);
  30.             ll frwrd=(w-l);
  31.             ll cost2=abs(a[i]*bb-(pfx[l-1]-pfx[i]))+abs(frwrd*(n+a[i])-(pfx[w-1]-pfx[l-1]));
  32.             //ll bb=r-i;               ALTERNATE
  33.             //ll frwrd=(w-r-1);
  34.             //ll cost2=abs(a[i]*bb-(pfx[r]-pfx[i]))+abs(frwrd*(n+a[i])-(pfx[w-1]-pfx[r]));
  35.             l=0;r=i-1;
  36.             while(l<=r)
  37.             {
  38.                 mid=(l+r)/2;
  39.                 cur=a[mid];
  40.                 if((target-cur)>=(n-target+cur))l=mid+1;
  41.                 else r=mid-1;
  42.             }
  43.             ll inc=i-1;
  44.             ll dec=l;
  45.             ll cost1=abs(inc*a[i]-(pfx[i-1]-((l>=1)?pfx[l-1]:0)))+abs(dec*(n-a[i])+((l>=1)?pfx[l-1]:0));
  46.             ans=min(ans,cost1+cost2);
  47.         }
  48.         cout<<"Case #"<<query<<": "<<ans<<endl;
  49.     }
  50. }
  51.  
Success #stdin #stdout 0s 4332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case #1: 94648683790773
https://ideone.com/0jY4Ko
language:
C++ (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!