当前位置:首页 > 资讯 > info5 > 正文

FZU 2178 礼物分配 (折半搜索+二分)

发表于: 2015-01-29   作者:u013013910   来源:转载   浏览:
摘要: 题目地址:FZU2178由于n最大是30,一次全搜的话妥妥的超时,那么可以采用折半搜索。分成相同的两份,对左边的一堆进行预处理,然后再处理右堆,每一次都对左堆进行二分,找最接近的。由于两个人取的不能相差多于1个,所以要对每个个数分开存储。并排序,排序是为了后边的二分。代码如下:#include #include #include #include #include #include #includ

题目地址:FZU 2178

由于n最大是30,一次全搜的话妥妥的超时,那么可以采用折半搜索。分成相同的两份,对左边的一堆进行预处理,然后再处理右堆,每一次都对左堆进行二分,找最接近的。由于两个人取的不能相差多于1个,所以要对每个个数分开存储。并排序,排序是为了后边的二分。

代码如下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=1e9;
const double eqs=1e-9;
int v[40], w[40], c[17][1<<15], d[17];
int bin_search(int x, int f)
{
        int low=0, mid, high=d[f]-1, ans=-1;
        while(low<=high){
                mid=low+high>>1;
                if(c[f][mid]>=x) {
                        ans=mid;
                        high=mid-1;
                }
                else low=mid+1;
        }
        if(ans==-1){
                return abs(c[f][d[f]-1]-x);
        }
        else if(ans==0){
                return abs(c[f][0]-x);
        }
        else return min(abs(c[f][ans]-x),abs(c[f][ans-1]-x));
}
int main()
{
        int t, n, i, min1, tot, m1, m2, ans1, ans2, al, ans, j, cnt;
        //freopen("1.txt","r",stdin);
        //freopen("2.txt","w",stdout);
        scanf("%d",&t);
        while(t--){
                scanf("%d",&n);
                m1=n>>1;
                m2=n-m1;
                min1=INF;
                for(i=0;i<n;i++){
                        scanf("%d",&v[i]);
                }
                for(i=0;i<n;i++){
                        scanf("%d",&w[i]);
                }
                if(n==1){
                        printf("%d\n",min(v[0],w[0]));
                        continue ;
                }
                tot=1<<m1;
                memset(d,0,sizeof(d));
                memset(c,0,sizeof(c));
                for(i=0;i<tot;i++){
                        ans1=ans2=cnt=0;
                        for(j=0;j<m1;j++){
                                if(i&(1<<j)) {
                                                ans1+=v[j];
                                                cnt++;
                                }
                                else ans2+=w[j];
                        }
                        c[cnt][d[cnt]++]=ans1-ans2;
                }
                for(i=0;i<=m1;i++){
                        sort(c[i],c[i]+d[i]);
                }
                al=1<<m2;
                for(i=0;i<al;i++){
                        ans1=ans2=0;
                        cnt=0;
                        for(j=0;j<m2;j++){
                                if(i&(1<<j)) {
                                                ans1+=v[j+m1];
                                                cnt++;
                                }
                                else ans2+=w[j+m1];
                        }
                        ans=ans2-ans1;
                        //printf("%d\n",ans);
                        if((n&1)&&cnt){
                                min1=min(bin_search(ans,n/2+1-cnt),min1);
                        }
                        min1=min(bin_search(ans,n/2-cnt),min1);
                }
                printf("%d\n",min1);
        }
        return 0;
}


FZU 2178 礼物分配 (折半搜索+二分)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
二分查找(折半查找): 从有序序列中找到给出的要查询的数字。 原理是:首先把一个有序序列中间位置
Problem 2039 Pets Accept: 395 Submit: 1061 Time Limit: 1000 mSec Memory Limit : 32768 KB Prob
二分搜索 简单的问题串联可以组成复杂! 给定已经排好序的n个元素a[0...n-1],现在在这n个元素中找
 J - Min Number Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Subm
排序算法二:二分(折半)插入排序算法 声明:引用请注明出处http://blog.csdn.net/lg1259156776/
Java 常用排序算法/程序员必须掌握的 8大排序算法 本文由网络资料整理转载而来,如有问题,欢迎指正
Problem Description Are you interested in pets? There is a very famous pets shop in the cente
礼物... 《礼物》 -- 许巍 让我怎么说 我不知道 太多的语言 消失在胸口 头顶着蓝天 沉默高原 有你在
K Best Time Limit: 8000MS Memory Limit: 65536K Total Submissions: 5288 Accepted: 1431 Case Ti
分治法的基本思想:将一个规模为n的问题,分解为k个规模较小的子问题,这些子问题互相独立且与原问
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号