二分题单
两个比较重要的函数:
lower_bound：在一个有序序列中进行二分查找，返回指向第一个 大于等于 $x$的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。
lower_bound(v.begin(),v.end(),x)
upper_bound：在一个有序序列中进行二分查找，返回指向第一个 大于 $x$的元素的位置的迭代器。如果补存在这样的元素，则返回尾迭代器。
upper_bound(v.begin(),v.end(),x)
手写lower_bound和upper_bound二分
若未找到返回0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int lower_bound(int val)
{
int l=1,r=n,res=0;
while(l<=r)
{
int mid=l+((r-l)>>1);
if(a[mid]<=val)res=mid,l=mid+1;
else r=mid-1;
}
return res;
}
int upper_bound(int val)
{
int l=1,r=n,res=0;
while(l<=r)
{
int mid=l+((r-l)>>1);
if(a[mid]<val)res=mid,l=mid+1;
else r=mid-1;
}
return res;
}
|
P2249 查找
P2249 【深基13.例1】查找 - 洛谷
二分做法
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
|
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int n,m,a[MAXN];
int query(int val)
{
int l=1,r=n;
int ans=-1;
while(l<=r)
{
int mid=l+((r-l)>>1);
if(a[mid]>=val)ans=mid,r=mid-1;
else l=mid+1;
}
if(a[ans]==val)return ans;
else return -1;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)
{
int val;
cin>>val;
cout<<query(val)<<' ';
}
}
|
map统计做法
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
|
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e9+10;
int n,m;
unordered_map <int,int> mp;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
if(!mp.count(a))mp[a]=i;
}
for(int i=1;i<=m;i++)
{
int val;
cin>>val;
if(!mp.count(val))cout<<"-1 ";
else cout<<mp[val]<<' ';
}
return 0;
}
|
P1102 A-B 数对
P1102 A-B 数对 - 洛谷
二分查询+记忆化
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
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=2e5+10;
int n,c,a[MAXN];
unordered_map <int,int> mp;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>c;
for(int i=1;i<=n;i++)
{
cin>>a[i];
mp[a[i]]++;
}
int ans=0;
for(int i=1;i<=n;i++)
ans+=mp[a[i]-c];
cout<<ans;
return 0;
}
|
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
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=2e5+10;
int n,a[MAXN],c;
unordered_map <int,int> mp;
int query(int val)
{
if(mp.count(val))return mp[val];
int l=1,r=n;
int ans=-1;
while(l<=r)
{
int mid=l+((r-l)>>1);
if(a[mid]>=val)ans=mid,r=mid-1;
else l=mid+1;
}
if(a[ans]!=val)return -1;
int cnt=0;
for(int i=ans;i<=n;i++)
if(a[i]==a[ans])cnt++;
else break;
mp[val]=cnt;
return cnt;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>c;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n,less<int>());
int ans=0;
for(int i=1;i<=n;i++)
{
int res=query(a[i]+c);
if(res!=-1)ans+=query(a[i]+c);
}
cout<<ans;
return 0;
}
|
P1678 烦恼的高考志愿
P1678 烦恼的高考志愿 - 洛谷
二分查找
须考虑后一个大学是否有更优答案
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
|
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e5+10;
int n,m,dx[MAXN];
int lower_bound(int val)
{
int l=1,r=n,ans=0;
while(l<=r)
{
int mid=l+((r-l)>>1);
if(dx[mid]<=val)ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
int ans=0;
for(int i=1;i<=n;i++)cin>>dx[i];
sort(dx+1,dx+1+n,less<int>());
for(int i=1;i<=m;i++)
{
int xs;
cin>>xs;
int pos=lower_bound(xs);
int a1,a2;
if(pos==0)ans+=abs(dx[1]-xs);
else if(pos==n)ans+=abs(dx[n]-xs);
else ans+=min(abs(dx[pos]-xs),abs(dx[pos+1]-xs));
}
cout<<ans;
return 0;
}
|
P1824 [USACO05FEB] 进击的奶牛 Aggressive Cows G
进击的奶牛 - 洛谷
二分答案
check当前的距离mid能不能分出$m$头奶牛
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
|
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,m,a[MAXN],b[MAXN];
bool check(int val)
{
int lstcow=1,cnt=1;
for(int i=2;i<=n;i++)
if(a[i]-a[lstcow]>=val)
lstcow=i,cnt++;
return cnt>=m;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n,less<int>());
int l=1,r=a[n],ans;
while(l<=r)
{
int mid=l+((r-l)>>1);
if(check(mid))ans=mid,l=mid+1;
else r=mid-1;
}
cout<<ans;
return 0;
}
|
P2678 [NOIP 2015 提高组] 跳石头
[P2678 NOIP 2015 提高组] 跳石头 - 洛谷
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
|
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e4+10;
int L,n,m,a[MAXN];
bool check(int val)
{
int lst=0,cnt=0;
for(int i=1;i<=n+1;i++)
if(a[i]-a[lst]>=val)lst=i;
else cnt++;
return cnt<=m;
}
signed main()
{
cin>>L>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
a[n+1]=L;
int l=1,r=L,ans;
while(l<=r)
{
int mid=l+((r-l)>>1);
if(check(mid))ans=mid,l=mid+1;
else r=mid-1;
}
cout<<ans;
return 0;
}
|
P2440 木材加工
P2440 木材加工 - 洛谷
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
|
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,m,a[MAXN];
bool check(int val)
{
if(val==0)return 0;
int cnt=0;
for(int i=1;i<=n;i++)cnt+=(a[i]/val);
return cnt>=m;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
int l=0,r=100000010,ans=0;
while(l<=r)
{
int mid=l+((r-l)>>1);
if(check(mid))ans=mid,l=mid+1;
else r=mid-1;
}
cout<<ans;
return 0;
}
|