我也不是B(倍增二分

玲珑杯 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+2n)
进行二分即可。

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

/* ***********************************************************************
  > 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,如果顾及并使用,可能会有麻烦。