PTA:人以群分 (25分) (C语言版)

川长思鸟来 2023-07-18 09:56 52阅读 0赞

社交网络中我们给每个人定义了一个“活跃度”，现希望根据这个指标把人群分为两大类，即外向型（outgoing，即活跃度高的）和内向型（introverted，即活跃度低的）。要求两类人群的规模尽可能接近，而他们的总活跃度差距尽可能拉开。

输入格式：  
输入第一行给出一个正整数N（2≤N≤10  
5  
 ）。随后一行给出N个正整数，分别是每个人的活跃度，其间以空格分隔。题目保证这些数字以及它们的和都不会超过2  
31  
 。

输出格式：  
按下列格式输出：

Outgoing \#: N1  
Introverted \#: N2  
Diff = N3

其中N1是外向型人的个数；N2是内向型人的个数；N3是两群人总活跃度之差的绝对值。

输入样例1：  
10  
23 8 10 99 46 2333 46 1 666 555

输出样例1：  
Outgoing \#: 5  
Introverted \#: 5  
Diff = 3611

输入样例2：  
13  
110 79 218 69 3721 100 29 135 2 6 13 5188 85

输出样例2：  
Outgoing \#: 7  
Introverted \#: 6  
Diff = 9359

#include <stdio.h>
    #include <stdlib.h>
    
    int comfunc(const void *elem1, const void *elem2);
    void sort_character(int *p, int n);
    
    int main()
    { 
    	int n, i;
    	int a[100001];
    	
    	scanf("%d", &n);
    	for (i = 0; i < n; i++)
    		scanf("%d", &a[i]);
    	qsort(a, n, sizeof(int), comfunc);
    	sort_character(a, n);	
    	
    	return 0;
    }
    
    int comfunc(const void *elem1, const void *elem2)
    { 
    	int *p1 = (int*)elem1;
    	int *p2 = (int*)elem2;
    	
    	return *p1 - *p2;	
    }
    void sort_character(int *p, int n)
    { 
    	int i, j, n1, n2, sum1, sum2, dif, dif1, dif2;
    	
    	sum1 = sum2 = 0; dif = dif1 = dif2 = 0;
    	if (n % 2 == 0)
    	{ 
    		n1 = n2 = n / 2;
    		for (i = 0; i < n1; i++)
    			sum1 += p[i];
    		for (i = n1; i < n; i++)
    			sum2 += p[i]; 
    		dif = abs(sum2 - sum1);
    	}
    	else
    	{ 
    		n1 = n2 = n / 2;
    // dif1 = abs(p[n1] - p[n1 - 1]); //总活跃度差值！！！ 不是两个之间之差。 
    // dif2 = abs(p[n2] - p[n2 + 1]); 
            for (i = 0; i < n1; i++)
            	sum1 += p[i];
            for (i = n / 2 + 1; i < n; i++)
            	sum2 += p[i];
            dif1 = abs(sum1 + p[n1] - sum2);
            dif2 = abs(sum2 + p[n2] - sum1);
            dif = (dif1 > dif2) ? dif1 : dif2;
    		 if (dif1 > dif2)
    		 	n1++;
    		 else
    		 	n2++;
    	}
    	printf("Outgoing #: %d\n", n2);
    	printf("Introverted #: %d\n", n1);
    	printf("Diff = %d\n", dif);
    	
    }