L2-1. 人以群分

怼烎@ 2022-06-18 00:46 138阅读 0赞

L2-1. 人以群分

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

输入格式：

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

输出格式：

按下列格式输出：

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

/\*  
分析:  
1.输入数组  
2.排序  
3.判断奇偶  
4.累加 输出  
\*/

#include <iostream> 
    #include <cmath>
    #include <algorithm>
    int cmp(int a,int b){
       return a > b;} //从大往小排 用于sort模板排序 
    using namespace std;
    int main()
    {   
        int n;
        cin >> n;
        int *arr = new int [n+1];
        int n1,n2;
        int sum1 = 0,sum2 = 0;
        for(int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        sort(arr+1, arr+n+1, cmp);
        if(n % 2 == 0){ //偶数 
            n1 = n/2;
            n2 = n/2;
            for(int i = 1; i <= n1; i++){
                sum1 += arr[i]; 
            }   
            for(int i = n1+1; i <= n; i++){
                sum2 += arr[i];
            }
        } else{         //奇数 
            if( arr[n/2-1]-arr[n/2] > abs(arr[n/2]-arr[n/2+1] )) {  //靠近内向 
                n1 = n/2;
                n2 = n/2+1; 
            } else {    //靠近外向 
                n1 = n/2+1;
                n2 = n/2;
            }
            for(int i = 1; i <= n1; i++){
                sum1 += arr[i]; 
            }   
            for(int i = n1+1; i <= n; i++){
                sum2 += arr[i];
            }
    
        }
        cout << "Outgoing #: " << n1 << endl;
        cout << "Introverted #: " << n2 << endl;
        cout << "Diff = " << sum1-sum2;
        return 0;
    }