[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 E: qwb和李主席 [折半枚举二分]【思维?套路!】
[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 E: qwb和李主席 [折半枚举二分]【思维?套路!】
2017-06-03 02:17:40 Tabris_ 阅读数:1339
博客爬取于2020-06-14 22:40:19
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72849660
题目链接:http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=4
——————————————————————————————————————————
Problem E: qwb和李主席
Time Limit: 4 Sec Memory Limit: 128 MB
Submit: 391 Solved: 39
[Submit][Status][Web Board]
Description
qwb和李主席打算平分一堆宝藏,他们想确保分配公平,可惜他们都太懒了,你能帮助他们嘛?
Input
输入包含多组测试数据,处理到文件结束。
每组测试数据的第一行是一个正整数N(0 <= N <=36 )表示物品的总个数.。
接下来输入N个浮点数(最多精确到分),表示每个物品的价值V(0< V<=1e9)。
Output
对于每组测试数据,输出能够使qwb和李主席各自所得到的物品的总价值之差的最小值(精确到分),每组测试数据输出占一行。
Sample Input
3 0.01 0.1 1
2 1 1
Sample Output
0.89
0.00
——————————————————————————————————————————
n=36,如果直接枚举的话超时
然后先到分成两部分进行枚举,先枚举出一部分的所有可能结果,然后枚举另一部分在这个部分二分找最优就好
找的时候要找加和最靠近total/2的,然后维护最小值就好了
讲道理说如果*100用整形处理比较美滋滋,但是wa到死,改成double直接ac。。。。
附本题代码
——————————————————————————————————————————
1 | # include <bits/stdc++.h> |