首页 > 其他分享 >F. Rudolf and Imbalance

F. Rudolf and Imbalance

时间:2024-03-14 20:48:11浏览次数:28  
标签:return read ll mid len flag Imbalance Rudolf

原题链接

题解

最大值最小 \(\to\) 二分可行性判断:
二分间断值 \(len\ \to\) 如果原序列 \(a_i-a_{i-1}>len\) \(\to\) 双指针判断有没有 \(b+f\) 使得 \(a_i-len<=b+f<=a_{i-1}+len\)
由于只能使用一次,所以若使用两次也算错

code


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

#define ll long long
ll a[100005]={0},d[200005]={0},f[200005]={0};
ll n,m,k;

inline void read(ll &x) {
    x = 0;
    ll flag = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x)
{
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

ll in(ll l,ll r)
{
    ll j=k;
    for(ll i=1;i<=m;i++)
    {
        while(j&&d[i]+f[j]>r)j--;
        if(!j) return 0;
        if(d[i]+f[j]>=l) return 1;
    }
    return 0;
}

ll check(ll maxlen)
{
    ll flag=0;
    for(ll i=2;i<=n;i++)
    {
        if(a[i]-a[i-1]>maxlen)
        {
            if(flag)return 0;
            flag=1;
            if(!in(a[i]-maxlen,a[i-1]+maxlen)) return 0;
        }
    }
    return 1;
}

int main()
{
    ll t;
    read(t);
    while(t--)
    {
        read(n); read(m); read(k);
        ll l=-1,r=0;

        for(ll i=1;i<=n;i++)
        {
            read(a[i]);
            if(i>1) r=max(a[i]-a[i-1],r);
        }
        for(ll i=1;i<=m;i++) read(d[i]);
        for(ll i=1;i<=k;i++) read(f[i]);
        sort(d+1,d+m+1);
        sort(f+1,f+k+1);
        while(l+1<r)
        {
            ll mid=(l+r)>>1; 
            if(check(mid)) r=mid;
            else l=mid;
        }
        write(r); putchar('\n');
    }
    return 0;
}

···

标签:return,read,ll,mid,len,flag,Imbalance,Rudolf
From: https://www.cnblogs.com/pure4knowledge/p/18073898

相关文章

  • Paper Reading: Density‑based weighting for imbalanced regression
    目录研究动机文章贡献本文方法DenseWeight稀有度度量权重函数DenseLoss实验结果实验整体的设置合成数据集实验实验设置实验结果对比实验实验设置降水量预测任务优点和创新点PaperReading是从个人角度进行的一些总结分享,受到个人关注点的侧重和实力所限,可能有理解不到位的地方。......
  • Paper Reading: Oversampling with Reliably Expanding Minority Class Regions for I
    目录研究动机研究背景研究目的文章贡献本文方法可靠的扩展少数类区域的过采样方法描述方法分析多分类的OREM-MOREM和Boosting的结合计算复杂度实验结果二分类数据集实验实验设置对比实验消融实验调参实验多分类数据集实验对比实验消融实验OREMBoost实验实验设置对比实验优点......
  • CF1902 A Binary Imbalance 题解
    LinkCF1902ABinaryImbalanceQuestion给出一个01串,可以在任意一个位置\(i\)插入一个字符,如果\(a_i\nea_{i+1}\)插入的字符为\(0\)否则插入的字符为\(1\)问,是否可以通过任意次操作使得串中\(0\)的数量比\(1\)多Solution如果一个串都为\(0\)肯定符合都......
  • CF1846E2 Rudolf and Snowflakes (hard version) 题解
    题意:\(T\)\((\)\(1\)\(\le\)\(T\)\(\le\)\(10^4\)\()\)组询问:是否存在一个满\(k\)(\(k\)\(\ge\)\(2\)\()\)叉树节点数恰好为\(n\)\((\)\(1\)\(\le\)\(n\)\(\le\)\(10^{18}\)\()\),且深度\(depth\)至少为\(2\)。思路:满$k$......
  • Paper Reading: Sample and feature selecting based ensemble learning for imbalanc
    目录研究动机文章贡献本文方法基于聚类的分层随机欠采样特征选择样本和特征选择的集成学习基于随机森林的SFSHEL实验结果数据集和实验设置KEEL数据集的比较HeartFailure数据集的比较优点和创新点PaperReading是从个人角度进行的一些总结分享,受到个人关注点的侧重和实力所限......
  • CF1852B Imbalanced Arrays 题解
    CF1852BImbalancedArrays题解Links洛谷CodeforcesDescription对于一个给定的长度为\(n\)的数组\(A\),定义一个长度为\(n\)的数组\(B\)是不平衡的当且仅当以下全部条件满足:\(-n\leqB_{i}\leqn\)且\(B_{i}\ne0\)。即每个数在\([-n,n]\)内且不为\(0\)。......
  • Paper Reading: Hashing-Based Undersampling Ensemble for Imbalanced Pattern Class
    目录研究动机文章贡献本文方法整体流程基于哈希的子空间划分方法基于距离的样本选择实验结果数据集和实验设置不同子空间划分方法的影响不同加权方案的抽样与其他方法比较优点和创新点PaperReading是从个人角度进行的一些总结分享,受到个人关注点的侧重和实力所限,可能有理解不到......
  • 【题解】Imbalanced Arrays - Codeforces 1852B
    出处:CodeforcesRound887链接:https://codeforces.com/problemset/problem/1852/B题目大意:给定一个包含\(n\)个非负整数的频次序列\(f\)。构造任意一个等长的整数序列\(b\),要求①\(b\in[-n,n]\)but$b\neq0$②\(b\)中不存在相反数③对于每个坐标\(i\)......
  • Paper Reading: Self-paced Ensemble for Highly Imbalanced Massive Data Classifica
    目录研究动机文章贡献分类硬度分布分类硬度的定义分类硬度的优点分类硬度视角下的样本类型本文方法自定步速欠采样硬度协调自定步速因子算法定义实验结果合成数据集实验数据集和实验设置合成数据实验结果类重叠下的鲁棒性真实数据集实验数据集和实验设置真实数据实验结果和重采样......
  • codeforces-817 D. Imbalanced Array(单调栈)
    题意:求数组中每个连续子序列的的最大值-最小值之和。思路:题意可以理解为加上每一个序列的最大值,减去每一个序列的最小值。每个数都可以作为某一连续子序列的最大值和最小值,所以可以枚举每一个数作为最值的区间,暴力枚举时间复杂度过高,所以利用单调栈找出每个数左边或右边第一个比......