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