[数据结构与算法]L2-017 人以群分 (25 分)（c语言实现）

该题目如下

如题所示，其中会先给数据的个数，所以先进行数据的录入，利用数组来存储数据中的活跃度，同时利用一个n来记录数组中元素的个数。

数据录入过程：

int n1, n2, n3;
int n = 0;
scanf("%d", &n);
int arr[100000];
for (int i = 0; i < n; i++)
{
	scanf("%d", &arr[i]);
}

排序在这里选用库函数自带的qsort，否则不能达到该题所要求的时间要求（测试点四），手打快排无法满足该题时间要求

qsort（数组名，数组中元素的个数，数组每个元素所占的字节数量，自定义的inc函数）

代码实现如下

#include <stdio.h>
#include <stdlib.h>
int inc(const void* a, const void* b)
{
	return *(int*)a - *(int*)b;
}
//此为自定义的inc函数，qsort在比较不同类型的数据的时候需要不同类型的自定义inc函数
int main()
{
	int n1, n2, n3;
	int n = 0;
	scanf("%d", &n);
	int arr[100000];
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	qsort(arr, n - 1, sizeof(arr[0]), inc);
}

到这一步完成对数组的排序

根据题目要求，理解如下

n1代表外向人数，n2代表内向人数

而数组已经被我们排序，所以只需要从数组中提取需要的数据并相加即可

意为先从数组的前端提取n2个数字，记为sum1，然后剩余的数字为另一组记为sum2

由于数组已经被排序，所以我们清楚地知道sum2与sum1的大小必然是sum2>sum1，所以在这里不需要利用绝对值函数，直接进行sum2-sum1即可

代码的实现如下

#include <stdio.h>
#include <stdlib.h>
int inc(const void* a, const void* b)
{
	return *(int*)a - *(int*)b;
}
int main()
{
	int n1, n2, n3;
	int n = 0;
	scanf("%d", &n);
	int arr[100000];
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	qsort(arr, n-1,sizeof(arr[0]),inc);
	int sum1 = 0, sum2 = 0;
	if (n % 2 == 0)
	{
		n1 = n2 = n / 2;
		for (int i = 0; i < n1; i++)
		{
			sum1 += arr[i];
		}
		for (int m = n1; m < n; m++)
		{
			sum2 += arr[m];
		}
	}
	else
	{
		n1 = (n / 2) + 1;
		n2 = n / 2;
		for (int i = 0; i < n1-1; i++)
		{
			sum1 += arr[i];
		}
		for (int m = n1-1; m < n; m++)
		{
			sum2 += arr[m];
		}
	}
    n3 = sum2 - sum1;
	printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d",n1,n2,n3);
}

利用手打快排能保证最终结果正确，但是无法通过测试点4

手打快排实现如下

#include <stdio.h>
#include <math.h>
void quickSort(int* array, int left, int right)
{
	if (NULL == array)
	{
		return;
	}

	if (left < right)
	{
		int pivot = array[left];
		int low = left, high = right;
		while (low < high)
		{
			while (array[high] >= pivot && low < high)
				high--;
			array[low] = array[high];

			while (array[low] <= pivot && low < high)
				low++;
			array[high] = array[low];
		}
		array[low] = pivot;

		quickSort(array, left, low - 1);
		quickSort(array, low + 1, right);
	}
}
int main()
{
	int n1, n2, n3;
	int n = 0;
	scanf("%d", &n);
	int arr[100000];
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	quickSort(arr, 0, n - 1);
	int sum1 = 0, sum2 = 0;
	if (n % 2 == 0)
	{
		n1 = n2 = n / 2;
		for (int i = 0; i < n1; i++)
		{
			sum1 += arr[i];
		}
		for (int m = n1; m < n; m++)
		{
			sum2 += arr[m];
		}
		n3 = sum2 - sum1;
	}
	else
	{
		n1 = (n / 2) + 1;
		n2 = n / 2;
		for (int i = 0; i < n1-1; i++)
		{
			sum1 += arr[i];
		}
		for (int m = n1-1; m < n; m++)
		{
			sum2 += arr[m];
		}
		n3 = sum2 - sum1;
	}
	printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d",n1,n2,n3);
}