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)


相关推荐

  • shiro面试知识点总结_jmeter面试常见问题

    shiro面试知识点总结_jmeter面试常见问题Shiro总结和常见面试题一、 什么是shiroShiro是一个强大易用的java安全框架,提供了认证、授权、加密、会话管理、与web集成、缓存等功能,对于任何一个应用程序,都可以提供全面的安全服务,相比其他安全框架,shiro要简单的多。二、 Shiro的核心概念Subject、SecurityManager、RealmSubject:主体,代表了当前“用户”,这个用户不一定是一个具体的…

    2022年10月14日
  • 字典的创建必须使用dict()函数(vba dictionary 嵌套)

    巧用枚举类型来管理数据字典背景开发Java项目时,数据字典的管理是个令人头痛的问题,至少对我而言是这样的,我所在的上一家公司项目里面对于字典表的管理是可以进行配置的,他们是将字典表统一存放在一个数据库里面进行配置,然后可以由管理员进行动态的实现字典表的变更.一般而言先来两个实体类学生类Studentpackagecn.cpf.entity;/***@Author…

  • 使用KNN识别MNIST手写数据集(手写,不使用KNeighborsClassifier)

    KNN识别MNIST手写数据集(32*32维),根据KNN原理一步步实现。

  • 分节符后页眉如何更改与上一节相同_页眉和页脚是什么

    分节符后页眉如何更改与上一节相同_页眉和页脚是什么不常编辑对文档有格式要求的朋友来说,偶尔需要编辑指定格式页眉页码的word文档时,会一时不记得如何使用,在网上搜索半天,异常烦躁。特整理一下,记录下来,备不时只需。以下操作环境为word2016。

  • QTreeView样式[通俗易懂]

    QTreeView样式[通俗易懂]1、无样式2、设置被选中节点的字体颜色和背景颜色QTreeView::item:selected{color:#E7ECF0;background:qlineargradient(spread:pad,x1:0,y1:0,x2:0,y2:1,stop:0#667481,stop:1#566373);}3、设置悬浮节点的字体颜色和背景颜色QTreeView::item:hover{color:#ffffff;background:#ff0000;}4、设置节点的上下左右的内

  • 常用的测试用例设计方法有那些类型_测试用例设计

    常用的测试用例设计方法有那些类型_测试用例设计扎实的基础是成功的一半,学号好基础,才能更好的进步!常见的测试用例设计方法主要会涉及以下几种:1、等价类2、边界值3、场景法4、判定表5、因果图6、错误推断法7、正交测试法(正交表)(今天主要解释前三种最为常用)选择合适的测试用例方法,有助于你去更好的梳理出逻辑关联关系,让你的测试覆盖率更高,更高效率的覆盖到所有测试点。一、等价类划分法1)定义依据需求输入划分为若干等价类,从等价类中选定一个测试…

    2022年10月11日

发表回复

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

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