question:社交网络中我们给每个人定义了一个“活跃度”，现希望根据这个指标把人群分为两大类，即外向型（outgoing，即活跃度高的）和内向型（introverted，即活跃度低的）。要求两类人群的规模尽可能接近，而他们的总活跃度差距尽可能拉开。
tips:关键点在于如何处理分界点 想想是不是可以用几何中的距离呢
输入格式：
输入第一行给出一个正整数N（2≤N≤105）。随后一行给出N个正整数，分别是每个人的活跃度，其间以空格分隔。题目保证这些数字以及它们的和都不会超过2^31
输出格式：
1
2
3
| Outgoing #: N1
Introverted #: N2
Diff = N3
|
其中N1是外向型人的个数；N2是内向型人的个数；N3是两群人总活跃度之差的绝对值。
输入样例1：
1
2
| 10
23 8 10 99 46 2333 46 1 666 555
|
AC代码如下：（tips 如果你是PTA30题的人并且恰好搜到了此博客 请勿抄袭 抄袭的话会被举报）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include <iostream>
#include <algorithm>
#include <malloc.h>
#include <cstdio>
#include <cstdlib>
using namespace std;
int main()
{
int a;
scanf("%d",&a);
int *c=(int*)malloc(sizeof(int)*a);
for(int i=0;i<a;i++)
{
scanf("%d",&c[i]);
}
sort(c,c+a);
int flag1=0,flag2=0;
int sum1=0;
int sum2=0;
if(a%2==0)
{
flag1=a/2;
flag2=a/2;
for(int i=0;i<flag1;i++)
{
sum1+=c[i];
}
for(int i=flag1;i<a;i++)
{
sum2+=c[i];
}
}
else{
int mid=a/2;
if((c[mid]-c[mid-1])<=(c[mid+1]-c[mid]))
{
flag1=mid;
flag2=a-flag1;
}
else
{
flag1=mid+1;
flag2=a-flag1;
}
for(int i=0;i<flag1;i++)
{
sum1+=c[i];
}
for(int i=flag1;i<a;i++)
{
sum2+=c[i];
}
}
cout<<"Outgoing #: "<<flag2<<endl;
cout<<"Introverted #: "<<flag1<<endl;
cout<<"Diff = "<<abs(sum1-sum2);
}
|