首页 > 其他分享 >SS241109B. tii(tii)

SS241109B. tii(tii)

时间:2024-11-09 14:58:36浏览次数:1  
标签:ld int SS241109B mn tii ans rk

SS241109B. tii(tii)

题意

给你一个 \(01\) 序列,长度为 \(n \le 5\times 10^5\)。给你一个小数 \(p\),要你找出一个区间满足区间 \(1\) 的个数比区间长度和 \(p\) 最接近,输出区间的左端点,如果有多个区间输出左端点最小的那个。

思路

设 \(s\) 是原序列的前缀和数组,翻译一下题面就是求 \(|p-\frac{s_r-s_l}{r-l}|\) 最小,输出 \(l+1\)。

算一下式子:

\[|p-\frac{s_r-s_l}{r-l}|=|\frac{(pr-s_r)-(p_l-s_l)}{r-l}| \]

这相当于两点斜率绝对值最小,\((i,pi-s_i)\)。

观察发现,\(s_i\) 每次可能增加 \(1\) 或者不变,\(pi\) 每次增加 \(p<1\),因此可以画出函数 \(pi-s_i\) 的图像。

要使两点间斜率最小,发现一定是选择 \(y\) 坐标相邻的两点。感性理解?

然后就对点排个序,再 \(O(n)\) 扫一遍更新答案即可。

时间复杂度是 \(O(n\log n)\),瓶颈在于排序。

code

代码很好写啊。

注意精度问题,因此判断相等和小于需要根据 eps 判断,尤其注意小于的细节:

bool less (ld a,ld b) { return b-a>eps; }
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace Vivid {
    constexpr int N=5e5+7,base=1e6;
    typedef long double ld;
    constexpr ld inf=1e9,eps=1e-10;
    int t,n;
    ld p;
    int b[N];
    char a[N]; 
    ld c[N];
    int rk[N];
    bool cmp (int a,int b) { return c[a]!=c[b]  ? c[a]<c[b] : a<b; }
    int ans;
    ld mn;
    ld abs(ld x) { return x>=0 ? x : -x; }
    bool equal (ld a,ld b) { return abs(a-b)<=eps; }
    bool less (ld a,ld b) { return b-a>eps; }
    void main() {
        sf("%d",&t);
        while(t--) {
            mn=inf;
            ans=0;
            sf("%d%Lf%s",&n,&p,a+1);
            rk[0]=0;
            rep(i,1,n) b[i]=b[i-1]+a[i]-'0', c[i]=p*i-b[i], rk[i]=i;
            sort(rk,rk+n+1,cmp);
            rep(i,1,n) {
                ld x=abs((c[rk[i]]-c[rk[i-1]])/(rk[i]-rk[i-1]));
                if(less(x,mn)) ans=min(rk[i-1],rk[i]), mn=x;
                else if(equal(x,mn)) ans=min(ans,min(rk[i-1],rk[i]));
            }
            pf("%d\n",ans+1);
        }
    }
}
int main() {
    #ifdef LOCAL
    freopen("my.out","w",stdout);
    #else 
    freopen("tii.in","r",stdin);
    freopen("tii.out","w",stdout);
    #endif
    Vivid :: main();
}

标签:ld,int,SS241109B,mn,tii,ans,rk
From: https://www.cnblogs.com/liyixin0514/p/18536814

相关文章

  • PARTIII-Oracle事务管理-事务
    10.事务10.1.事务简介10.1.1.示例事务:账户借记和贷记10.1.2.事务的结构10.1.3.语句级原子性10.1.4.系统变更号(SCNs)10.2.事务控制概述10.2.1.事务名称10.2.2.活跃事务10.2.3.保存点10.2.4.事务回滚10.2.5.事务提交10.3.自治事务10.4.分布式事务10.4.1.......
  • PARTIII-Oracle事物管理-数据并发性和一致性
    9.数据并发性和一致性本章解释了Oracle数据库如何在多用户数据库环境中维护一致性的数据。本章包含以下部分:数据并发性和一致性的介绍Oracle数据库事务隔离级别的概述Oracle数据库锁定机制的概述自动锁定的概述手动数据锁定的概述用户定义锁的概述9.1.数据并发性和一......
  • PARTII-Oracle数据访问-SQL
    7.SQL7.1.SQL简介7.1.1.SQL数据访问7.1.2.SQL标准7.2.SQL语句概述7.2.1.数据定义语言(DDL)7.2.2.数据操作语言(DML)7.2.3.事务控制语句7.2.4.会话控制语句7.2.5.7.3.优化器概述7.3.1.优化器用途7.3.2.优化器的组件7.3.3.访问路径7.3.4.优化器统计信息7.3......
  • 如何通过MultiIndex查询MultiIndex并选择“最佳”行?
    假设我有一个MultiIndexbyMultiIndexDataFrame类似于这里生成的:importpandasaspddata_frame_rows=pd.MultiIndex.from_arrays([[],[],[]],names=("car","engine","wheels"))data_frame_columns=pd.MultiIndex.fr......
  • python DataFrame之MultiIndex 的使用
    importpandasaspdimportpprintasp#嵌套列表arrays=[['a','a','b','b'],[1,2,1,2]]#创建MultiIndexindex=pd.MultiIndex.from_arrays(arrays,names=('letter','number'))#使用MultiInd......
  • 报错org.activiti.engine.ActivitiIllegalArgumentException: resource 'bpmn/file.bp
    一、代码段及报错位置1.代码段2.报错文件位置  二、报错原因:org.activiti.engine.ActivitiIllegalArgumentException:resource'bpmn/file.bpmn'notfound  三、解决方法:将resources-->bpmn-->file.bpmn复制粘贴到target-->classess-->bpmn下:......
  • Pandas操作MultiIndex合并行列的Excel,写入读取以及写入多余行及Index列处理,插入行,修改
    Pandas操作MultiIndex合并行列的excel,写入读取以及写入多余行及Index列处理1.效果图及问题2.源码参考今天是谁写Pandas的复合索引MultiIndex,写的糊糊涂涂,晕晕乎乎。是我呀…记录下,现在终于灵台清明了。明天在记录下直接用openpyxl生成合并单元格,事半功倍。跟......
  • RTII
    运行时类型识别即RTTI主要由一下两个运算符实现typeid,返回表达式类型dynamic_cast,将基类指针或引用安全地转换成派生类指针或引用运算符会自动使用指针或引用对象的动态类型。特别适用于想用基类指针或引用来执行派生类的不是虚函数的操作,即无法使用虚函数的情况。但实际上尽......
  • 十年携手ODCC开放数据中心!浪潮信息发布OpenBMC和OTII最新技术成果
    近日,由开放数据中心委员会(ODCC)主办的2023“开放数据中心大会”在北京国际会议中心举行。今年是ODCC成立10周年,大会汇集了数据中心产业链上下游企业、科研机构、专家学者等共同见证发展成果。浪潮信息也在会上发布了基于OpenBMC 、OTII标准的两项最新技术成果,以软硬件协同创新,支......
  • 自动检测MultiIndex的维数并全部转化为整数
    将pd.MultiIndex.from_tuples(  [(int(a),int(b))fora,binmy_df.index],  names=my_df.index.names)改写为自动检测MultiIndex的维数并全部转化为整数的函数importpandasaspdimportnumpyasnp#YouroriginalDataFramemy_df=pd.DataFrame(np.add......