152.c

来自「平时acm训练时ac的源代码」· C语言 代码 · 共 69 行

/*152
Accepted 83 ms 234 kb 
*/

#include <stdio.h>
#include <stdlib.h>


int ShellSort(unsigned long *l[],int n)
{
	unsigned long *t;
	int i, j, k, h, q, *ll;
	ll = (int *)malloc(sizeof(int) * n);
	for (q=0, i=n; i>1; q++, i=i/2)
	{
		ll[q]=i/2;
	}
	for (i=0; i<q; i++)
	{
		h=ll[i];
		for (j=h; j<n; j++)
		{
			t=l[j];
			for (k=j-h; k>=0 && *t>*l[k]; k-=h)
			{
				l[k+h]=l[k];
				l[k]=t;
			}
		}
	}
	free(ll);
}

int main()
{
	unsigned long N, *A, i, *R, la, **Ap;
	unsigned long S=0, RS=0;
	scanf("%lu", &N);
	A = (unsigned long *)malloc(sizeof(unsigned long) * N);
	R = (unsigned long *)malloc(sizeof(unsigned long) * N);
	Ap = (unsigned long **)malloc(sizeof(unsigned long *) * N);
	for (i=0; i<N; i++)
	{
		Ap[i] = &R[i];
	}
	for (i=0; i<N; i++)
	{
		scanf("%lu", &A[i]);
		S += A[i];
	}
	for (i=0; i<N; i++)
	{
		R[i] = (A[i]*100)/S;
		RS += R[i];
	}
	la = 100-RS;
	ShellSort(Ap,N);
	for (i=0; i<la; i++)
	{
		*Ap[i] += 1;
	}
	for (i=0; i<N; i++)
	{
		printf("%lu ", R[i]);
	}
	free(A);
	free(R);
}