程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> FZU 2178 禮物分配 (折半搜索+二分)

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

編輯：C++入門知識

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

題目地址：FZU 2178

由於n最大是30，一次全搜的話妥妥的超時，那麼可以采用折半搜索。分成相同的兩份，對左邊的一堆進行預處理，然後再處理右堆，每一次都對左堆進行二分，找最接近的。由於兩個人取的不能相差多於1個，所以要對每個個數分開存儲。並排序，排序是為了後邊的二分。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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