POJ3061 Subsequence(二进制前缀和法律+仿真足)

POJ3061 Subsequence(二进制前缀和法律+仿真足)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

二分法+前缀和法律

满足子序列长度的条件(0,n)之间,sum[x+i]-sum[i]从i元素开始序列长度x和。前缀和可在O(n)的时间内统计

sum[i]的值。再用二分找出满足条件的最小的子序列长度。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cmath>
#define ll __int64
#define INF 0x3fffffff
using namespace std;

int sum[100005];
int a[100005];
int n,s;

bool C(int x)
{
    bool flag=false;
    for(int i=0;i<n-x;i++)
    {
        if(sum[x+i]-sum[i]>=s)
        {
            flag=true;
            break;
        }
    }
    if(flag) return true;
    else return false;
}

int solve()
{
    int l=0,r=n+1;
    while(r-l>1)
    {
        int mid=(l+r)/2;
        if(C(mid)) r=mid;
        else l=mid;
    }
    return r;
}

int main()
{
    int T;
    //freopen("d:\\Test.txt","r",stdin);
    cin>>T;
    while(T--)
    {
        cin>>n>>s;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        sum[0]=a[0];
        for(int i=1;i<n;i++)
        {
            sum[i]=sum[i-1]+a[i];
        }
        if(solve()==n+1) cout<<"0"<<endl;
        else cout<<solve()<<endl;
    }
    return 0;
}

尺取法

(1)  设置两个指针s和t。一開始都指向数列第一个元素。此外sum=0,res=0。

(2)  仅仅要sum<S。就将sum添加一个元素,t加1;

(3)  直到sum>=S,更新res=min(res,t-s);

(4)  将sum减去一个元素。s加1,运行(2)。

上述流程重复地推进区间的开头和末尾,来求取满足条件的最小区间。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int a[100005];

void solve()
{
    int res=n+1;
    int s=0,t=0,sum=0;
    while(true)
    {
        while(t<n&&sum<m)
        {
            sum+=a[t++];
        }
        if(sum<m) break;
        res=min(res,t-s);
        sum-=a[s++];
    }
    if(res>n) res=0;
    cout<<res<<endl;
}

int main()
{
	int T;
    //freopen("d:\\Test.txt","r",stdin);
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        solve();
    }
    return 0;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117508.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • GitHub上传文件不能超过100M的解决办法

    GitHub上传文件不能超过100M的解决办法

    2021年10月15日
  • 斗战神 拳猴刷图加点

    斗战神 拳猴刷图加点是输出手法,我觉得这个一般来说争议不大,但是很重要一点,BOSS战开始前,一定保证身上有一个蛮横的BUFF,如上图所示。至于顺序分别是:九豆或满豆起手-乱星舞-八荒-极影腿×2-巨猿-神行-

  • django常见问题_二级报错了怎么办

    django常见问题_二级报错了怎么办报错情况Django使用makemigrations做数据迁移的时候报如下错误File"/Users/jkc/.virtualenvs/django_env/lib/python3.7

  • python面试常见问题-Python面试中最常见的25个问题

    python面试常见问题-Python面试中最常见的25个问题Python部落(python.freelycode.com)组织翻译,禁止转载,欢迎转发。Python是一个面向对象的解释型的交互式高级脚本语言。Python被设计成一种高可读性的语言,因为它大量地使用了英语中的单词作为关键字,而且不像其他语言使用标点符号构成复杂的语法结构,Python的语法结构非常少。Python是一种解释型语言:即Python程序是在运行时由解释器解释执行的,因而不用事先编…

    2022年10月19日
  • pytest重试_pytest失败重跑

    pytest重试_pytest失败重跑安装:pip3installpytest-rerunfailures重新运行所有失败用例要重新运行所有测试失败的用例,请使用–reruns命令行选项,并指定要运行测试的最大次数:$py

  • 华为管理学案例分析_华为战略管理案例分析.docx[通俗易懂]

    华为管理学案例分析_华为战略管理案例分析.docx[通俗易懂]华为战略管理案例分析华为战略管理案例分析制作组成员:樊欣宇2410024李燕华2410024马路遥2410024王定徐侃班级:工商管理班(战略与运营系)目录第一部分华为简介愿景使命公司战略发展简史腾飞的华为华为标识产品服务管理体系附:任正非简介第二部分SWOT分析外部环境分析PEST分析产业环境分析(波特五力模型)内部条件分析优势和劣势分析核心竞争力分析SWOT分析第三部分管理模式分析第四部分企业…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号