二分

你真的会二分么

Posted on

这次我敢打包票我是真的 ~~完全~~ 进了一大步了解了二分。

这个内容对在座的各位大佬来说肯定还是很简单的,菜鸡现在才搞懂,个人还是觉得是有里程碑的意义的。

1.元素完全确定的二分查找

这是二分查找的最简单形式,就是你要查找的值确定,且不重复。
这种形式下,只要找到这个值直接返回即可。

int binarySearch(int le, int ri, int val)
{
    int mid;
    while (le <= ri) {
        mid = (le + ri) >> 1;
        if (ary[mid] == val)
            return mid;
        else if (ary[mid] > val)
            ri = mid - 1;
        else
            le = mid + 1;
    }
    return -1;
}

2.给定条件的二分查找

举个栗子,求出某个有序序列中最小的比val大的数,第一个等于val的下标等等……

这种二分查找当我们找到一个满足约束条件的值时,我们就尝试着去扩大这个约束极限,使得它更满足我们的条件。我这里可能表述不清楚,比如 ary[idx] > val ,假设序列递增 , 那么可以尝试让idx向右移动。

而对于初学者来说,可能会有两个很困惑的地方。

2.1 最后的二分的结果究竟 取 l ? r ?

当然如果是浮点数二分的话,直接返回 mid 即可

曾经我拿这个问题去问学长,学长说看情况,所以我拖到了现在。
其实我用一句话概括的话,==就是你最后一个满足条件的 mid ==。

我这里举个栗子,查找某个递增序列中最小的比val大的数。

int binarySearch(int le, int ri, int val)
{
    int mid, rlen = ri + 1;
    while (le <= ri) {
        mid = (le + ri) >> 1;
        if (ary[mid] > val) //此时的ary[mid] 满足约束条件
            ri = mid - 1;
        else
            le = mid + 1;
    }
    return ri == rlen ? -1 : ary[ri + 1]; //若val比ary[0]还小,那么ary[0]是满足要求的。
                                          //但如果数组中不存在比val大的数,就要特判一下。
                                          // mid = ri+1 就是在二分过程中最后一个满足约束条件的 idx
}
2.2 在while循环的时候,\( le \le ri \) 还是 \(le \lt ri\)

首先我们可以确定的是,在浮点数二分的时候,这个等于并不会给我们带来太大影响。
而不管是浮点数还是整型数,加了一个等于都能是我们进一步扩大极限的机会。

哦,说白了,其实这个我也不是很清楚,你只要把 = 加上去肯定是没错的……

这个坑以后回来再填。

二分

我也不是B(倍增二分

Posted on

玲珑杯 Round #13 B题

DESCRIPTION

小 L 有一串 Q 个数排成一排,从左往右是 A1 开始一直到 AQ,它一直很喜欢这串数。

有一天,小 L 去高考报名了,小 J 和小 N 过来用这串数玩游戏。

一开始,小 N 手上有一个空序列,定义变量C:=0
。小 J 从左往右依次把序列中的数取出,放到小 N 手上序列的最右边,如果放完之后,整个序列的混乱度超过了 M,小 N 就会把手上的所有数全部扔掉,然后令 C:=C+1。

定义一个长度为 K,序列的混乱度 S=K∑i=1Bi×Vi,其中 Bi 表示序列中第 i 小的数,V
为一个给定的序列。

小 J 和小 N 想知道,加入每个数之后,C是多少。

题意
很好理解就不说了

思路
说实话这道题拿到手,我只是傻傻的遍历+优先队列做。毫无疑问就 T 了。最后T了4发就滚去睡午觉了。

看了题解竟然是二分!以当前位置对后续位置二分,满足这个区间的混乱度都小于等于 K。

完全没想到二分的辣鸡已经开始颤抖,然而这道题用的却是倍增二分,单纯的二分复杂度还是太高了。

对当前位置 idx ,我枚举 2^n 使得 [idx,idx+2^n]这个区间混乱度大于 K ,再对 [idx+2^(n-1),idx+2^n)
进行二分即可。

说实话,倍增二分我以前真的从未听闻,今天见到也是长了见识。

/* ***********************************************************************
  > File Name: lonlife.cpp
  > Author: Key
  > Mail: keyld777@gmail.com
  > Created Time: Mon 03 Apr 2017 02:34:09 PM CST
 ********************************************************************** */

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const int maxn = 1000010; //不知道为什么  数组大小调成 3e5+10 会RE 索性增大到 1e6+10

long long a[maxn], v[maxn], ans[maxn], tmp[maxn], n, k;

bool Traversal(int st, int en)
{
    int len = 0;
    for (int i = st; i <= en; i++)
        tmp[++len] = a[i];
    sort(tmp + 1, tmp + len + 1);
    long long tmp_ans = 0;
    for (int i = 1; i <= len; i++) {
        tmp_ans += (tmp[i] * v[i]);
        if (tmp_ans > k)
            return true;
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int p;

    while (cin >> n >> k) {
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 1; i <= n; i++)
            cin >> v[i];
        int idx = 1, key = 0;
        while (idx <= n) {
            for (p = 1; idx + p <= n; p <<= 1)
                if (Traversal(idx, idx + p))
                    break;
            int l = idx + p / 2, r = idx + p, mid;
            while (l < r) {
                mid = (l + r) >> 1;
                if (Traversal(idx, mid))
                    r = mid;         //因为要维护的是一个  左闭右开区间
                else
                    l = mid + 1;
            }
            for (; idx <= l; idx++) {
                if (idx == l) {
                    ans[idx++] = ++key;
                    break;
                }
                ans[idx] = key;
            }
        }
        for (int i = 1; i < n; i++)
            cout << ans[i] << " ";
        cout << ans[n] << endl;
    }
    return 0;
}

顺便说一点个人对二分的看法:

在一直二分下去不跳出的情况下,并且也是正常标准写法的时候,left,mid与right都是会无限接近的。
当循环条件为left < right 时 最终 left必然与right相等,如果是 left<=right 则最终结果则必然为left+1 = right。

==而mid的最终结果不好判断==

举个例子 如果我在 left < right 的某个最终状态前 left=50 right=51 则 mid=50。 而在之后的条件判断下,有可能会使left=mid+1 则最终结果为 left=right=51 mid=50……

这样说的话,也许我们应该在循环结束后再加个 (left+right)>>1 才能确保mid必定与left与right中的一个相等……

总而言之,(个人觉得),在运用二分算法不中途跳出的情况下,最终结果不必顾及mid,如果顾及并使用,可能会有麻烦。

二分

HDU 4355 Party All the Time

Posted on

暑假集训选拔马上就要开始了

挺虚的,就临时抱一下佛脚

把以前没有写的周练补一下,从最开始补起,也就是二分三分

没想到一下子就A了,说明还是有点长进的,哈哈,可喜可贺,可喜可贺

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define eps 1e-6

using namespace std;

inline double cal(double a,double b)
{
    if(a<0) a=-a;
    return a*a*a*b;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        int n;
        double x[50100],w[50100],l=1000000,r=-1000000,mid,midmid,ans=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&x[i],&w[i]);
            l=min(l,x[i]);
            r=max(r,x[i]);
        }
        while(eps+l<=r)
        {
            mid=(l+r)/2;
            midmid=(l+mid)/2;
            double msum=0,mmsum=0;
            for(int i=0;i<n;i++)
            {
                msum+=cal(mid-x[i],w[i]);
                mmsum+=cal(midmid-x[i],w[i]);
            }
            if(msum+eps<mmsum) l=midmid;
            else r=mid;
            ans=min(msum,mmsum);
        }
        printf("Case #%d: %.0f\n",k,ans);
    }
    return 0;
}