X03ADAY1
2025-08-02 14:56:18
发布于：浙江
27阅读
0回复
0点赞
二分算法
二分查找
假设表元素是按升序排列
将 查找范围的中间元素的值 和 目标元素 作比较，利用中间位置将表分成前后两个子表
- 如果
查找范围的中间值==目标元素，则查找成功 - 如果
目标元素<查找范围中间值，范围缩小到前一子表 - 如果
目标元素>查找范围中间值，则查找范围缩小到后一子表
重复以上过程，直到目标元素，则查找成功 直到子表不存在为止，则查找失败
二分查找时间复杂度：
第一个大于等于指定值的元素 lower_bound(a+1,a+n+1,x)-a 得到的是下标（如无大于等于对应元素的值，输出最大下标n+1）
第一个大于指定值的元素 upper_bound(a+1,a+n+1,x)-a 得到的是下标（如无大于对应元素的值，输出最大下标+1->n+1）
二分答案
二分答案与二分查找类似，二分查找有一个前提就是数列是有序的，二分答案要求满足条件的答案是单调有序的，它的基本思路是当前答案是否满足题目的要求，根据检查结果更新查找区间，最终取得最符合题目要求的答案进行输出
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
long long n,m;
long long a[N];
bool check(long long mid){
long long sum=0;
for(long long i=1;i<=n;i++){
if(a[i]>mid){
sum+=a[i]-mid;
}
}return sum>=m;
}
int main(){
long long mx=0;
cin>>n>>m;
for(long long i=1;i<=n;i++){
cin>>a[i];
mx=max(mx,a[i]);//同一数据类型
}
long long l=0/*锯掉所有木头*/,r=mx;
long long ans=0;
while(l<=r){
long long mid=(l+r)/2;
if(check(mid)){
l=mid+1;//r=mid-1;
ans=mid;
}else{
r=mid-1;
}
}cout<<ans<<endl;
}
前缀和
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int a[maxn];
int pre[maxn];
int main(){
/*int n,l,r,a[100010]={0},q,sum=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
cin>>q;
for(int i=1;i<=q;i++){
sum=0;
cin>>l>>r;
for(int i=l;i<=r;i++){
sum+=a[i];
}
cout<<sum<<endl;
}*/
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int q;cin>>q;
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+a[i];
}for(int i=1;i<=q;i++){
int R,L;
cin>>L>>R;
cout<<pre[R]-pre[L-1]<<endl;
}
}
差分
#include<bits/stdc++.h>
using namespace std;
int a[100010],d[100010];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}for(int i=1;i<=n;i++){
d[i]=a[i]-a[i-1];
}while(m--){
int l,r,c;
cin>>l>>r>>c;
d[l]+=c;
d[r+1]-=c;
}
for(int i=1;i<=n;i++){
a[i]=a[i-1]+d[i];
cout<<a[i]<<" ";
}
}
#include<bits/stdc++.h>
using namespace std;
int n,a[20],cnt;
bool vis[20];
bool prime(int n){
if(n<=1)return 0;
for(int i=2;i<n;i++){
if(n%i==0)return 0;
}
return 1;
}
void dfs(int x){
if(x>n){
int sum=0;
for(int i=1;i<=n;i++){
if(vis[i])sum+=a[i];
}
if(prime(sum))cnt++;
return ;
}
vis[x]=1;
dfs(x+1);
vis[x]=0;
dfs(x+1);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dfs(1);
cout<<cnt;
}
有帮助，赞一个