PAT A1113 Integer Set Partition (25 分)——排序题
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
#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn=;
int seq[maxn];
int total[maxn];
int main(){
int n;
int sum=;
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%d",&seq[i]);
}
sort(seq,seq+n);
for(int i=;i<n;i++){
sum+=seq[i];
total[i]=sum;
}
printf("%d %d",n%,total[n-]-*total[n/-]);
}
注意点:计算差的时候由于总和算了前面部分,要多减一次前半部分。感觉直接算和然后相减也不会超时
最新文章
- Cesium应用篇:2影像服务(下)
- shell parameter expansitions
- golang笔记——命令
- NSArray 所有基础点示例
- javaSE之Object及hashcode等相关知识
- 收藏所用C#技术类面试、笔试题汇总
- springMVC视频教程
- 退出telnet
- [liu yanling]软件测试技巧
- HW2.23
- WordPress get_allowed_mime_types函数(wp-includes/functions.php)存在跨站脚本漏洞
- HDU ACM 1066 Last non-zero Digit in N!
- CSS媒体查询适配范例
- sql优化策略之索引失效情况二
- JavaScript 六大类运算符(详细~)
- linux基础 用户(组)管理
- 网络请求(I)
- windows BLE编程 net winform 连接蓝牙4.0
- PHP 操作 Redis 的手册
- Java的进阶之道
热门文章
- [转*译]Networking API Improvements in Windows 10
- 在UAP中如何通过WebView控件进行C#与JS的交互
- 前端学习 之 Bootstrap (一)
- SFTP 文件配置
- ajax请求完之前的loading加载
- loadrunner&#160;运行脚本-Run-time&#160;Settings->;General->;Additional&#160;attributes设置
- Spark内存分配诊断
- ASP.NET MVC从请求到响应发生了什么
- Mvc检查图片格式后上传
- LCD显示异常分析——撕裂(tear effect)【转】