XP03B - day02

集团-陈超杰

2026-08-03 20:54:50

发布于：广东

74阅读

0回复

0点赞

砍树动画演示链接

奶茶热量

小码君干饭记

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,q;
long long a[N],pre[N];
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+a[i];
    }
    while(q--){
        long long x;
        cin>>x;
        int ans=upper_bound(pre+1,pre+n+1,x)-pre-1;
        cout<<ans<<'\n';
    }
    return 0;
}

vector + 二分函数笔记

1. vector 动态数组

vector<int> a;

添加：

a.push_back(x);

长度：

a.size()

访问：

a[i]

2. sort 排序

升序：

sort(a.begin(),a.end());

降序：

sort(a.begin(),a.end(),greater<int>());

3. lower_bound

找第一个：

>= x

int p=lower_bound(a.begin(),a.end(),x)-a.begin();

4. upper_bound

找第一个：

> x

int p=upper_bound(a.begin(),a.end(),x)-a.begin();

5. 统计 x 出现次数

upper_bound(x)-lower_bound(x)

例：

int ans=upper_bound(a.begin(),a.end(),x)
       -lower_bound(a.begin(),a.end(),x);

注意：

使用 lower_bound / upper_bound 前必须排序

复杂度：

sort        O(nlogn)
二分查找    O(logn)

砍树

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n,m;
int a[N];
bool check(int x){
    long long ans = 0;
    for(int i=1;i<=n;i++){
        ans += max(a[i]-x,0);
    }
    return ans>=m;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    int l = 0,r = 1e9,ans = 0;
    while(l<=r){
        int mid = (r-l)/2+l;
        if(check(mid)){
            l = mid+1;
            ans = mid;
        }else{
            r = mid-1;
        }
    }
    cout<<ans;
    return 0;
}

T8

T7

#include<bits/stdc++.h>
using namespace std;

const int N=110;
int n;
long long h;
long long a[N];
bool check(long long k){
    long long sum=k;
    for(int i=2;i<=n;i++)sum+=min(k,a[i]-a[i-1]);
    return sum>=h;
}
void solve(){
    cin>>n>>h;
    for(int i=1;i<=n;i++)cin>>a[i];
    long long l=1,r=h;
    long long ans=h;
    while(l<=r){
        long long mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }else l=mid+1;
    }
    cout<<ans<<'\n';
}
int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

数的三次方根

#include<bits/stdc++.h>
using namespace std;
int main(){
    double n;
    cin>>n;
    double l = -100,r = 100;
    // 至少保留6位小数
    // 1.000001
    // 1.000002
    while(r-l>1e-7){
        double mid = (l+r)/2;
        if(mid*mid*mid<=n){
            l = mid;
        }else{
            r = mid;
        }
    }
    printf("%.6f",l);
    return 0;
}