二分查找与二分答案
作业介绍
/*
有序
1 2 3 3 3 4 4 4 5 5 5 5
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n,a[N],q;
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=q;i++){
int x;
cin>>x;
int l=1,r=n;
int ans = -1;
while(l<=r){
int mid = (l+r)/2;
if(a[mid]<x){
l = mid+1;
}
else if(a[mid]==x){
ans = mid;
r = mid-1;
}
else if(a[mid]>x){
r = mid-1;
}
}
cout<<ans<<" ";
}
return 0;
}
/*
A
B = A-c
枚举第一个B的位置 d
枚举第一个大于B的位置 e
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n,a[N],A,B,c;
int find1(int x){
//返回第一个大于等于x的下标
int l=1,r=n,res=0;
while(l<=r){
int mid = (l+r)/2;
if(a[mid]>=x){
res = mid;
r = mid-1;
}
else l=mid+1;
}
return res;
}
int find2(int x){
//返回第一个大于x 的下标
int l=1,r=n,res=0;
while(l<=r){
int mid = (l+r)/2;
if(a[mid]>x){
res = mid;
r = mid-1;
}
else l = mid+1;
}
return res;
}
int main(){
cin>>n>>c;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
long long res = 0;
for(int i=1;i<=n;i++){
int A = a[i],B=A-c;
res+=find2(B)-find1(B);
}
cout<<res<<endl;
return 0;
}
/*
枚举举例x 判断举例x能否放下所有的牛
如果能放下,比x大一点
如果放不下,比x小一点
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,a[N],m;
int check(int x){
int now = a[1];
int cnt = 1;
for(int i=2;i<=n;i++){
if(a[i]-now>=x){
now = a[i];
cnt++;
}
}
if(cnt>=m)return 1;
else return 0;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
int l=1,r=1000000000,res=-1;
while(l<=r){
int mid = (l+r)/2;
if(check(mid)){
res = mid;
l = mid+1;
}
else r = mid-1;
}
cout<<res<<endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,k;
int a[N];
int check(int x){
//每一段切成x,能否切够k段
int cnt = 0;
for(int i=1;i<=n;i++){
cnt+=a[i]/x;
}
if(cnt>=k)return 1;
else return 0;
}
int main(){
cin>>n>>k;
long long sum = 0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
if(sum<k){
cout<<0<<endl;
return 0;
}
int l=1,r=100000000,res=-1;
while(l<=r){
int mid = (l+r)/2;
if(check(mid)){
res = mid;
l = mid+1;
}
else r= mid-1;
}
cout<<res<<endl;
return 0;
}
题目
认领作业后才可以查看作业内容。
- 状态
- 正在进行…
- 题目
- 13
- 开始时间
- 2026-4-19 0:00
- 截止时间
- 2026-6-30 23:59
- 可延期
- 24 小时