社交网络中我们给每个人定义了一个 "活跃度", 现希望根据这个指标把人群分为两大类, 即外向型 (outgoing, 即活跃度高的) 和内向型(introverted, 即活跃度低的). 要求两类人群的规模尽可能接近, 而他们的总活跃度差距尽可能拉开.
输入格式:
输入第一行给出一个正整数 N(2). 随后一行给出 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 <bits/stdc++.h>
- using namespace std;
- const int maxn = 1e5 + 10;
- int N;
- int a[maxn];
- int main() {
- scanf("%d", &N);
- for(int i = 1; i <= N; i ++)
- scanf("%d", &a[i]);
- sort(a + 1, a + 1 + N);
- int num1 = 0, num2 = 0;
- long long sum1 = 0, sum2 = 0, diff = 0;
- if(N % 2) {
- num1 = (N - 1) / 2;
- num2 = N - num1;
- for(int i = 1; i <= num1; i ++)
- sum1 += a[i];
- for(int i = num1 + 1; i <= N; i ++)
- sum2 += a[i];
- diff = sum2 - sum1;
- } else {
- num1 = num2 = N / 2;
- for(int i = 1; i <= num1; i ++)
- sum1 += a[i];
- for(int i = num1 + 1; i <= N; i ++)
- sum2 += a[i];
- diff = sum2 - sum1;
- }
- printf("Outgoing #: %d\n", num2);
- printf("Introverted #: %d\n", num1);
- printf("Diff = %lld\n", diff);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2768137.html