Problem B: Ultra-QuickSort
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence9 1 0 5 4 ,Ultra-QuickSort produces the output
0 1 4 5 9 .Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Este comentario ha sido eliminado por el autor.
ResponderEliminar/**
ResponderEliminar* Solución al problema 1810 Ultra-QuikSort
* de la uva online judge
* @author Catalina Valencia Hernández
* Facultad de Ciencias,UNAM
*/
#include
long long a[500002],b[500002];
int n=1;
long long dif,sum;
void mezcla(long long ini,long long med,long long fin)
{
int p1=ini,p2=med+1,p=0;
long long m=0;
while(p1<=med || p2<=fin)
{
if(p1<=med && p2<=fin)
{
if(a[p1]<=a[p2])
{
b[p]=a[p1];
p++;
p1++;
}
else
{
b[p]=a[p2];
dif=(p2-p1)-m;
sum+=dif;
m++;
p++;
p2++;
}
}
else if(p1<=med)
{
b[p]=a[p1];
p++;
p1++;
}
else
{
b[p]=a[p2];
p++;
p2++;
}
}
for(int i=0;iini)
{
int med=(ini+fin)/2;
divide(ini,med);
divide(med+1,fin);
mezcla(ini,med,fin);
}
}
int main()
{
while(n!=0)
{
scanf("%d",&n);
sum=0;
for(int i=0;i<n;i++)
scanf("%lld",&a[i]);
divide(0,n-1);
if(n!=0)
printf("%lld\n",sum);
}
return 0;
}