【PAT甲级 - C++题解】1113 Integer Set Partition

news/2024/10/31 3:20:46/

✍个人博客:https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址:PAT题解集合
📝原题地址:题目详情 - 1113 Integer Set Partition (pintia.cn)
🔑中文翻译:整数集合划分
📣专栏定位:为想考甲级PAT的小伙伴整理常考算法题解,祝大家都能取得满分!
❤️如果有收获的话,欢迎点赞👍收藏📁,您的支持就是我创作的最大动力💪

1113 Integer Set Partition

Given a set of N (>1) positive integers, you are supposed to partition them into two disjoint sets A1 and A2 of n1 and n2 numbers, respectively. Let S1 and S2 denote the sums of all the numbers in A1 and A2, respectively. You are supposed to make the partition so that ∣n1−n2∣ is minimized first, and then ∣S1−S2∣ is maximized.

Input Specification:

Each input file contains one test case. For each case, the first line gives an integer N (2≤N≤105), and then N positive integers follow in the next line, separated by spaces. It is guaranteed that all the integers and their sum are less than 231.

Output Specification:

For each case, print in a line two numbers: ∣n1−n2∣ and ∣S1−S2∣, separated by exactly one space.

Sample Input 1:

10
23 8 10 99 46 2333 46 1 666 555

Sample Output 1:

0 3611

Sample Input 2:

13
110 79 218 69 3721 100 29 135 2 6 13 5188 85

Sample Output 2:

1 9359

题意

给定 n 个数,将这 n 个数划分成两个集合 A1A2 ,其中 A1 包含 n1 个数且这些数之和为 s1A2 包含 n2 个数且这些数之和为 s2

现在需要我们使 |n2-n1| 的值尽可能的小,且 |s2-s1| 的值尽可能的大。

思路

直接上结论,我们只要将数组先排个序,然后尽可能均匀的分成两部分,所以 |n2-n1| 的值只可能为 01 ,且左半部分的值都是小于右半部分的,这样就能使 |s2-s1| 的值最大。

代码

#include<bits/stdc++.h>
using namespace std;const int N = 100010;
int w[N];
int n;int main()
{cin >> n;for (int i = 0; i < n; i++)    cin >> w[i];//进行排序sort(w, w + n);//计算两部分数值的和int s1 = 0, s2 = 0;for (int i = 0; i < n / 2; i++)  s1 += w[i];for (int i = n / 2; i < n; i++)  s2 += w[i];//输出结果cout << n % 2 << " " << s2 - s1 << endl;return 0;
}

http://www.ppmy.cn/news/6038.html

相关文章

四、网络层(七)网络层设备

目录 7.1 路由器的组成和功能 7.2 路由表与路由转发 7.1 路由器的组成和功能 路由器是一种具有多个输入/输出端口的专用计算机&#xff0c;其任务是连接不同的网络&#xff08;可以是异构的&#xff09;并完成路由转发。在多个逻辑网络&#xff08;即多个广播域&#xff…

高新技术企业认定的指标要求

高新技术企业认定的指标要求 1、拥有核心自主知识产权 &#xff08;通过自主研发&#xff0c;受让等方式&#xff09;拥有主营产品核心技术知识产权&#xff0c;数量要求&#xff1a;2项发明专利&#xff1b;10项实用新型专利软件著作版权。 2、产品&#xff08;服务&#x…

深度学习训练营之海贼王人物识别

深度学习训练营之海贼王人物识别原文链接环境介绍前置工作设置GPU导入数据数据查看数据预处理加载数据可视化数据检查数据配置数据集prefetch()功能详细介绍&#xff1a;归一化查看归一化后的数据构建VGG-16网络网络结构编译模型训练结果可视化原文链接 &#x1f368; 本文为&a…

解决资源消耗,top的运用记录

第一条命令uptime load average 后面的三个数字&#xff0c;分别代表1分钟、5分钟和15分钟内机器的平均负载 使用top命令解决负载问题 Cpu(s)这一行提供了CPU运行情况信息 这些缩写分别代表了不同含义 (1)us&#xff1a;用户CPU时间 运行非优雅的用户进程所占CPU时间的百…

2-2-3-9-1-1、jdk1.7HashMap详解

目录数据结构链表的作用链表问题数据结构简图源码解析重要成员变量说明构造函数put操作初始化数组Key为null的处理计算hash添加链表节点--新增Entry扩容缺点扩容死锁分析单线程扩容多线程扩容数据结构 jdk1.7的hashmap的底层结构是数组加单向链表实现的。将key的hash值进行取模…

ubuntu20.04 22.04下设置用户只能使用sftp, 不能登录ssh 的配置方法

vi /etc/ssh/sshd_config Match Group sftp ChrootDirectory %h ForceCommand internal-sftp AllowTcpForwarding no 如果是列出单独用户的写法&#xff1a; Match user yonghu1 ChrootDirectory /home/yonghu1/ ForceCommand internal-sftp X11Forwarding no AllowTcpForwa…

python连接mysql数据库

先安装pymysql管理工具 pip install pymysql 写一个py文件&#xff0c; vim ./my_sql.py 内容&#xff1a;&#xff08;数据库配置&#xff09; import pymysql dbpymysql.connect(hostlocalhost, userroot, password你的数据库密码 , databasewai_jian, port3306, charset…

序列化 反序列化

序列化 对象转换为二进制文件将 Java 对象转换成字节流的过程 1️⃣序列化过程&#xff1a;是指把一个 Java 对象变成二进制内容&#xff0c;实质上就是一个 byte[]。因为序列化后可以把 byte[] 保存到文件中&#xff0c;或者把 byte[] 通过网络传输到远程(IO)&#xff0c;如此…