专栏首页算法与数据结构PTA 人以群分(25 分)

PTA 人以群分(25 分)

7-2 人以群分(25 分)

社交网络中我们给每个人定义了一个“活跃度”,现希望根据这个指标把人群分为两大类,即外向型(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机智的我双开数组代表 + if 讨论 1A鲁老师的学生不许抄我的,我会被挂的。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL acv[100100],sum[100100];
int main()
{
    memset(acv,0,sizeof(acv));
    memset(sum,0,sizeof(sum));
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&acv[i]);
    }
    sort(acv+1,acv+1+n);
    sum[0]=0;
    for(int i=1;i<=n;i++){
        sum[i] = sum[i-1]+acv[i];
    }
    int a1 = n/2;
    int b1 = n-n/2;
    LL diff1 = 0;
    diff1 = sum[n] - 2*sum[a1];
    int b2 = n/2;
    int a2 = n-n/2;
    LL diff2 = 0;
    diff2 = sum[n] - 2*sum[a2];
    if(diff1>diff2){
        printf("Outgoing #: %d\n",b1);
        printf("Introverted #: %d\n",a1);
        printf("Diff = %lld\n",diff1);
    }
    else
    {
        printf("Outgoing #: %d\n",b2);
        printf("Introverted #: %d\n",a2);
        printf("Diff = %lld\n",diff2);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 拓扑排序 HDU - 5695

    众所周知,度度熊喜欢各类体育活动。  今天,它终于当上了梦寐以求的体育课老师。第一次课上,它发现一个有趣的事情。在上课之前,所有同学要排成一列, 假设最开始每...

    Kindear
  • CodeForces - 706B 二分stl

    #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<...

    Kindear
  • 栈与递归 实现 十进制转二进制

    6-4 十进制转换二进制(15 分) 本题要求实现一个函数,将正整数n转换为二进制后输出。 函数接口定义: void dectobin( int n ); 函数...

    Kindear
  • 问题:单片机软件仿真和实际运行速度不一样?

    如图,问题大概就是说初学单片机,用软件仿真出来的程序,在开发板上运行的效果比仿真的快,晶振都是一样的12M。还问到一个1T模式和12T模式的区别?

    单片机技术宅
  • 【总结】 几个C语言中的“坑”

    本题中的#运算符可以利用宏参数创建字符串。##运算符和#运算符一样也可以用于类函数宏的替换部分。另外,##还可以用于类对象宏的替换部分,这个运算符可以把两个语言...

    编程范 源代码公司
  • STM8S——Universal asynchronous receiver transmitter (UART)

    UART基本介绍: 通用异步收发器UART他的功能非常强大 我们只使用UART的全双工异步通信功能,使用中断接收数据。 UART_RX:串行数据输入。 UART...

    Christal_R
  • FHOG传统hog特征提取。FHOG

    关于HOG特征(梯度统计直方图)简单介绍一下,首先是对原图进行灰度化(hog统计的是梯度信息,色彩几乎没有贡献),再进行gamma压缩和归一化(减轻光照影响)。...

    和蔼的zhxing
  • linux sed指令详解

    新增多行内容,主要要是用到\或者回车(新增的内容使用单引号,如果要想使用回车来实现新增多行,注意另外一个单引号别写出来,否则就直接执行指令了)来新增多行内容

    我是李超人
  • 为什么会有人认为罗辑思维做了锤子手机?

    今天看到罗辑思维的人在朋友圈分享了一个截图,仔细看才能找到亮点:这篇文章说罗振宇做了“锤子手机”… ? 对于科技圈人士来说,这种张冠李戴让人哭笑不得。 互联网上...

    罗超频道
  • Python数据处理从零开始----第二章(pandas)⑧pandas读写csv文件(2)

    image.png 我们现在将学习如何使用Pandas read_csv并跳过x行数。 幸运的是,我们只使用skiprows参数非常简单。 在...

    用户1359560

扫码关注云+社区

领取腾讯云代金券