二分

发表于2021-10-12更新于2021-10-12阅读次数

据说只有10%的程序员能写对二分😮

二分的正确姿势

先看一个最简单的例子：

升序下，找第一个>=x的数

1
2
3
4
5
6
l=0,r=v.size();
while(l<r){
    ll mid=(l+r)>>1;
    if(v[mid]<x)  l=mid+1;//写二分的诀窍
    else  r=mid;
}

大多数情况下,l=0,r=v.size(),那我们接下来都在这种情况下讨论

  • 为什么mid是(l+r)>>1，不是(l+r+1)>>1；因为如果是后者,mid可能等于r，导致越界错误.

  • 由于mid每次靠近区间左端，所以对于v[ mid ] 后面接的肯定是l=mid+1，这样子很舒服(具体怎么解释不清楚。。)

  • 那么由前两点，我们只需要改中间的判断条件即可。

  • 注意升序对应>=x和>x，无<=x和 < x。因为升序导致了只能是>号

  • 一些模板：

  • 升序排序下：

  • 找第一个>=x的数

    1
    2
    3
    4
    5
    6
    l=0,r=v.size();
    while(l<r){
        ll mid=(l+r)>>1;
        if(v[mid]<x)  l=mid+1;
        else  r=mid;
    }

  • 找第一个>x的数

    1
    2
    3
    4
    5
    6
    l=0,r=v.size();
    while(l<r){
        ll mid=(l+r)>>1;
        if(v[mid]<=x)  l=mid+1;
        else  r=mid;
    }

  • 降序排序下：

  • 找第一个<=x的数

    1
    2
    3
    4
    5
    6
    l=0,r=v.size();
    while(l<r){
        ll mid=(l+r)>>1;
        if(v[mid]>x)  l=mid+1;
        else  r=mid;
    }

  • 找第一个< x的数

    1
    2
    3
    4
    5
    6
    l=0,r=v.size();
    while(l<r){
        ll mid=(l+r)>>1;
        if(v[mid]>=x)  l=mid+1;
        else  r=mid;
    }

4⭐二分好题-扎实的STL

Monopoly HDU - 7130
题意：由n<1e5个数排列成一个圆，一只猴子从第一个数开始，每走一步则得到该数的值。有m<1e5次询问，问得到x最少需要多少步

题解：

题解说可以用set写，但是估计是每次set插入的时候都要保证有序，比较耗时，导致t了，于是我用了map< ll,vector< P > >，全插入完之后再排个序，就快很多。

踩坑：
1.re:因为周期t可能很大，开始用的set,set[ x%t ]就re了
2.wa:负数取模一定要取模后再加上模数,直接取模再abs是错的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//set<ll> se[maxn];//这里t很大re了。。。。。。。
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=1e5+11;

ll sum[maxn],ar[maxn];
ll n,t,m;

map<ll,vector<P>> mp;
bool cmp(P a,P b){
    if(a.first!=b.first)  return a.first<b.first;
    return a.second>b.second;
}
void solve(ll x){
    ll b=abs((x%t+abs(t))%t);
    ll l=0,r=mp[b].size();
    while(l<r){
        ll mid=(l+r)>>1;
        if(mp[b][mid].first<=x)  l=mid+1;
        else  r=mid;
    }
    if(l==0){
        cout<<-1<<endl;return ;
    }
    l--;
    ll u=mp[b][l].first,v=mp[b][l].second;
    cout<<(x-u)/(abs(t))*n+v<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll ca;cin>>ca;
    while(ca--){
        mp.clear();
        ll q;cin>>n>>q;
        for(ll i=1;i<=n;i++)  cin>>ar[i];
        sum[0]=0;
        for(ll i=1;i<=n;i++)  sum[i]=sum[i-1]+ar[i];
        t=sum[n];
        if(t==0){
            for(ll i=0;i<=n;i++){
                if(mp.count(sum[i]))  continue;
                mp[sum[i]].push_back({sum[i],i});
            }
            for(ll i=1;i<=q;i++){
                ll x;cin>>x;
                if(mp.count(x))  cout<<mp[x][0].second<<endl;
                else  cout<<-1<<endl;
            }
            continue;
        }
        if(t<0){
            for(ll i=0;i<=n;i++)  sum[i]=-sum[i];
        }
        for(ll i=0;i<=n;i++){
            ll x=abs((sum[i]%t+abs(t))%t);//处理为负数的情况！不能直接%t就完事了
            mp[x].push_back({sum[i],i});
        }
        for(auto i=mp.begin();i!=mp.end();i++){
            sort(i->second.begin(),i->second.end(),cmp);
        }
        for(ll i=1;i<=q;i++){
            ll x;cin>>x;
            if(t<0)  x=-x;
            solve(x);
        }
    }
    return 0;
}