[原创]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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;
# define abs(x) (((x)>0)?(x):-(x))
const int N = 1000000+10;
const int MOD = 1e9+7;
const double INF = 1e18;
/******************************************/

double x[111];
double a[111],b[111],c[(1<<20)+1];
double tot,tmp,ans;
int la,lb,lc;int n;

double BS(){
    int l=1,r=lc,mid,res=-1;
    while(l<=r){
        mid = r+l >> 1;
        if(c[mid]+tmp>=tot/2.0)
            res=mid,r=mid-1;
        else l=mid+1;
    }
    if(res==-1) res=r;
    return min(abs(tot-c[res]*2-tmp*2),abs(tot-c[res-1]*2-tmp*2));
}

int main(){
    c[0]=INF;
    while(~scanf("%d",&n)){
        la=lb=lc=tot=0.0,ans=INF;
        for(int i=1;i<=n;i++) scanf("%lf",&x[i]);

        for(int i=1;i<=n;i++){
            tot+=x[i];
            if(i*2<=n) a[la++]=x[i];
            else       b[lb++]=x[i];
        }

        for(int i=0,j;i<(1<<la);i++)
            for(c[++lc]=0.0,j=0;j<la;j++)
                if(i&(1<<j)) c[lc]+=a[j];

        sort(c+1,c+lc+1);

        for(int i=0,j;i<(1<<lb);i++){
            for(tmp=0.0,j=0;j<lb;j++)
                if(i&(1<<j)) tmp+=b[j];
            ans=min(ans,BS());
        }
        if(ans==0.0) ans=0.0;
        printf("%.2f\n",ans);
//        printf("%lld.%02lld\n",ans/100,ans%100);
    }
    return 0;
}