Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int a[100100],n;
long long ans,s;

int dist(int x,int y)
{
    return a[y]-a[x]+(a[x]>a[y])*10000000;
}

int element(int x,int y)
{
    return y-x+1+(x>y)*n;
}

int main()
{
    int j,maxDif;
    cin >> n;
    for (int i=0;i<n;i++) scanf("%d",&a[i]), a[i]--;
    sort(a,a+n);
    maxDif=dist(n-1,0);
    for (int i=1;i<n;i++) maxDif=max(maxDif,dist(i-1,i));
    if (maxDif>dist(n-1,0))
    {
        for (j=1;j<n;j++)
            if (dist(j-1,j)==maxDif) break;
        for (int i=1;i<=n;i++) a[(j+i)%n]=dist(j,(i+j)%n);
        sort(a,a+n);
    }   
    for (int i=0;i<n;i++) 
        if (dist(0,i)<=5000000) s+=dist(0,i), j=i;
        else s+=dist(i,0);
    ans=s;
    for (int i=1;i<n;i++)
    {
        s-=1LL*element(i,j)*(a[i]-a[i-1]);
        while (1)
        {
            int jj=(j+1)%n;
            if (dist(i,jj)<=5000000 && jj!=i) 
            {
                j=jj;
                s-=min(dist(i-1,jj),dist(jj,i-1));
                s+=min(dist(i,jj),dist(jj,i));
            }
            else break;
        }
        s+=1LL*(n-element(i,j))*(a[i]-a[i-1]);
        ans=min(ans,s);
    }
    cout << ans << endl;
}

Code mẫu của RR

//Written by RR
#include <cstdio>
#include <cstdlib>
#include <algorithm>

#define MAXN 100111
#define oo 10000000
#define FOR(i,a,b) for(long i=a; i<=b; i++)

using namespace std;

typedef long long ii;

long n,a[MAXN];

void solve() {
     long startb=1,endb=n;
     while (endb>startb&&(oo-a[endb]+a[1]<a[endb]-a[1])) endb--;
     long long sum=0;
     FOR(i,1,endb) sum+=ii(a[i])-a[1];
     FOR(i,endb+1,n) sum+=ii(oo)-a[i]+a[1];
     long long res=sum;
     FOR(i,2,n) {
                //Nhom A: giam
                sum-=ii(a[i]-a[i-1])*(startb-1);
                //Nhom C: tang
                sum+=ii(a[i]-a[i-1])*(n-endb);
                //Nhom B
                sum+=ii(i-startb)*(a[i]-a[i-1]);
                sum-=ii(endb-i+1)*(a[i]-a[i-1]);
                //Thay doi phan B
                if (endb<i) {
                            sum-=oo;
                            endb=i;
                }
                while (startb<i&&(a[startb]+oo-a[i]<a[i]-a[startb])) {
                      sum-=ii(a[i]-a[startb])-(a[startb]+oo-a[i]);
                      startb++;
                }
                while (endb<n&&(oo-a[endb+1]+a[i]>a[endb+1]-a[i])) {
                      endb++;
                      sum-=(oo-a[endb]+a[i])-(a[endb]-a[i]);
                }
                res<?=sum;
     }
     printf("%lld\n",res);
}

int main() {
    #ifdef DEBUG
      freopen("input.txt","r",stdin);
      freopen("output.txt","w",stdout);
    #endif
    scanf("%ld",&n);
    FOR(i,1,n) scanf("%ld",&a[i]);
    sort(a+1,a+n+1);
    solve();
    return 0;
}

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#define maxp 10000000

void Quicksort(int A[],int lower,int upper)
{
        int x = A[(lower + upper) / 2];
        int i = lower;
        int j = upper;
        do{
                while(A[i] < x)
                        i ++;
                while (A[j] > x)
                        j --;
                if (i <= j)
                {
                     int tg=A[i];
                     A[i]=A[j];
                     A[j]=tg;   
                        i ++;
                        j --;
                }
        }while(i <= j);
        if (j > lower)
                Quicksort(A, lower, j);
        if (i < upper)
                Quicksort(A, i, upper);
}  

int n,a[200010];
long long KQ;

int main()
{
     //freopen("MSAFE.in","r",stdin);
     scanf("%d",&n);
     for(int i = 1;i<= n;i++) scanf("%d",&a[i]);
     Quicksort(a,1,n);
     for(int i = n+1;i<=2*n;i++) a[i] = a[i-n]+maxp;
     int r = 0,u = n+1; long long chay = 0;
     for(int i = 2;i<=n;i++)
     {
         if(a[i]-a[1]<=maxp/2)
         {
              r++;
              chay = chay+a[i]-a[1];
         }
         else 
         {  
              if(u==n+1)  u = i;
              chay = chay + a[n+1]-a[i];
         }
     }
     KQ = chay;
     for(int i = 2;i<=n;i++)
     {
         chay = chay+(a[i]-a[i-1])*(n-2*r);
         r--;
         while(a[u]-a[i]<maxp/2)
         {
             chay = chay-(maxp-2*(a[u]-a[i]));
             r++;
             u++;
         }
         if(chay<KQ) KQ = chay;
     }
     printf("%lld",KQ);
     //getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program MSAFE;
Const
  input  = '';
  output = '';
  maxv = 10000000;
  maxk = maxv div 2;
  maxn = 100000;
Type
  rec = record
    p,v: integer;
  end;
Var
  n: integer;
  a,sign: array[1..maxn] of integer;
  k: array[1..2 * maxn] of rec;
  min: int64;

Procedure init;
Var
  f: text;
  i: integer;
Begin
  Assign(f, input);
    Reset(f);

  Readln(f, n);
  For i:= 1 to n do
    Begin
      Read(f, a[i]);
      If a[i] < maxk + 1 then sign[i]:= -1 else sign[i]:= 1;
    End;
  Close(f);
End;

Procedure enter;
Var
  i: integer;
Begin
  For i:= 1 to n do
    Begin
      k[2 * i - 1].p:= a[i];
      k[2 * i - 1].v:= i;

      k[2 * i].p:= a[i] + maxk;
      If k[2 * i].p > maxv then k[2 * i].p:= k[2 * i].p - maxv;
      k[2 * i].v:= i;
    End;
End;

Procedure swap(var x,y: rec);
Var
  t: rec;
Begin
  t:= x;
  x:= y;
  y:= t;
End;

Procedure quicksort;

  Procedure partition(l,h: integer);
  Var
    i,j,pivot: integer;
  Begin
    If l >= h then exit;

    i:= l;
    j:= h;
    pivot:= k[random(h - l + 1) + l].p;

    Repeat
      While k[i].p < pivot do inc(i);
      While k[j].p > pivot do dec(j);

      If i <= j then
        Begin
          If i < j then swap(k[i],k[j]);
          inc(i);
          dec(j);
        End;
    Until i > j;

    partition(l,j);
    partition(i,h);
  End;

Begin
  partition(1,2 * n);
End;

Procedure solve;
Var
  i,pos,rate,tmp: integer;
  curr: int64;
Begin
  pos:= 1;
  curr:= 0;
  rate:= 0;

  For i:= 1 to n do
    Begin
      rate:= rate + sign[i];

      tmp:= abs(a[i] - pos);
      If tmp > maxk then tmp:= maxv - tmp;
      curr:= curr + tmp;
    End;

  min:= curr;
  For i:= 1 to 2 * n do
    Begin
      curr:= curr + (k[i].p - pos) * rate;
      If min > curr then min:= curr;
      pos:= k[i].p;

      tmp:= k[i].v;
      sign[tmp]:= -sign[tmp];
      rate:= rate + 2 * sign[tmp];
    End;
End;

Procedure printresult;
Var
  f: text;
Begin
  Assign(f, output);
    Rewrite(f);
    Writeln(f, min);
  Close(f);
End;

Begin
  init;
  enter;
  quicksort;
  solve;
  printresult;
End.