首页 > 其他分享 >poj 3061 Subsequence

poj 3061 Subsequence

时间:2024-05-17 22:42:21浏览次数:30  
标签:int sum Subsequence geqslant 3061 poj ans rm include

题目链接:

来自罗勇军《算法竞赛》书中的习题。
题意:给长度为 \(N\) 的数组和一个整数 \(S\),求总和不小于 \(S\) 的连续子序列的最小长度。

方法一:尺取法

主要思想为:当 \(a_1, a_2 , a_3\) 满足和 \(\geqslant S\),得到一个区间长度 \(3\), 那么去掉开头 \(a_1\),剩下 \(a_2,a_3\), 是否满足 \(\geqslant S\),如果满足,那么区间长度更新,如果不满足,那么尾部向后拓展,判断 \(a_2,a_3,a_4\) 是否满足条件。重复这样的操作。

主要分为四步:

  1. 如果 \(\rm sum<S\),就不断的放大 \(\rm right\),直到 \(\rm sum \geqslant S\) 或者 \(\rm right>N\)
  2. 如果第 \(1\) 步循环结束,\(sum<S\),程序结束,不走到 \(3\)
  3. 满足 \(\rm sum \geqslant S\),更新 \(\rm res=min(res,right-left)\)
  4. 放大 \(\rm left\) 回到 \(1\)

时间复杂度为 \(O(n)\).

\(\rm eg.\)
image

\(\rm ans=2\).

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int s[100005];

void solve() {
	int N, S;
	cin >> N >> S;
	for (int i = 1; i <= N; i++) {
		cin >> s[i];
	}
	int l = 1, r = 1, sum = 0, ans = N + 1;
	while (l <= r) {
		while (r <= N && sum < S) sum += s[r++];
		if (sum < S) break;
		ans = min(ans, r - l);
		sum -= s[l++];
	}
	if (ans == N + 1) cout << 0 << "\n";
	else cout << ans << "\n";
}

int main()
{
	int t = 1;
	cin >> t;
	while (t--) solve();
	return 0;
}

方法二、前缀和+二分

如果想要求出序列中某个连续子序列的和,我们可以采用前缀和的方式求出。得到前缀和之后,我们可以采取双循环枚举的方式枚举序列的所有子区间,从而得出合适的区间长度。但由于本题数据范围为 \(O(10^5)\),显然这样会超时。

for(int i = 1; i <= n; i ++) {
	for(int j = i; j <= n; j ++ ){
		if(sum[j] - sum[i - 1] >= s) {
			ans = min(ans,j - i + 1);
			break;
		} 
	}
}

分析第二重循环可以发现,我们只需要找到第一个满足 \(\rm sum[j] - sum[i - 1] \geqslant s\) 的就可以直接 \(\rm break\) 了,但是我们需要去枚举每一个 \(\rm sum[j]\),比较浪费时间,可以发现, \(\rm sum[x]\) 是一个递增的序列,这时候我们就可以采取二分的策略,寻找到第一个满足 \(\rm sum[j] - sum[i - 1] \geqslant s\) 的 \(j\)。时间复杂度为 \(O(nlogn)\).

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 1e5 + 10;

typedef long long LL;

LL sum[maxn], a[maxn];

int t, n, s; 

int main() {
	cin >> t;
	while(t --) {
		memset(sum,0,sizeof(sum));
		cin >> n >> s;
		for(int i = 1; i <= n; i ++) {
			cin >> a[i];
			// 前缀和 
			sum[i] = sum[i - 1] + a[i];
		}
		// 特判,如果整个序列和 < s,则一定没有合适的区间 
		if(sum[n] < s) puts("0");
		else {
			int ans = INF;
			for(int i = 1; i <= n; i ++) {
				int l = i;
				// 后面的判断没有意义,可以直接跳出循环 
				if(sum[n] - sum[l - 1] < s) break;
				int r = n;
				// 二分查找最小的右端点满足 sum[mid] - sum[i - 1] >= s 
				while(l < r) {
					int mid = l + r >> 1;
					if(sum[mid] - sum[i - 1] < s) l = mid + 1;
					else r = mid;
				}
				// 寻找到最小的区间 
				ans = min(ans,r - i + 1);
			}
			cout << ans<< endl;
		}
	}
	return 0;
}

参考文献:poj3061:Subsequence(最短子序列和) -- 前缀和与二分

标签:int,sum,Subsequence,geqslant,3061,poj,ans,rm,include
From: https://www.cnblogs.com/pangyou3s/p/18198823

相关文章

  • Mybatis逆向工程的2种方法,一键高效快速生成Pojo、Mapper、XML,摆脱大量重复开发
    一、写在开头最近一直在更新《Java成长计划》这个专栏,主要是Java全流程学习的一个记录,目前已经更新到Java并发多线程部分,后续会继续更新;而今天准备开设一个全新的专栏《EfficientFarm》。EfficientFarm:高效农场,期许软件开发工作能够像很多国外的高效农场一般机械化,自动化。拿来......
  • CF1966D Missing Subsequence Sum 题解
    题意:给定\(n(n\le10^6)\)和\(k(k\len)\)。构造一个长度小于等于\(25\)的序列\(a\)满足:1.不存在一个子序列的和为\(k\)。2.对于\(1\lei\len,i\nek\),存在一个子序列的和为\(i\)。看到长度为\(25\),首先肯定会想到二进制。那么我们先构造出一个序列\([2^......
  • Java(3)-POJO和Java bean的区别是什么
    POJO(PlainOldJavaObject)和JavaBean是两个密切相关但有细微差别的概念,在Java编程中经常被提及。这两者之间的主要区别在于它们的用途和设计要求。首先简单地介绍POJO是什么,POJO是"PlainOldJavaObject"的缩写,指的是一个普通的Java对象,它不依赖于特定的Java框架,也......
  • [atcoder 349] [F - Subsequence LCM]
    SOSDP学习笔记Linkhere:代码:importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.math.BigInteger;importjava.util.*;publicclassMain{staticintn;staticlongm;staticlong[]a;......
  • φ(* ̄0 ̄)3337. poj1845 sumdiv题解
    遇到数论题就要推式子!提供最美丽的latex\[a^b=p_1^{a_1*b}*p_2^{a_2*b}*p_3^{a_3*b}......*p_n^{a_n*b}\\那么他的因数之和为:\\({p_1}^0+{p_1}^1+...+{p_1}^{a_1*b})\\*({p_2}^0+{p_2}^1+...+{p_2}^{a_2*b})\\...\\*({p_n}^0+{p_n}^1+...+{p_n}^{a_n*b})\\=>利用等......
  • poj3696 The Luckiest number 题解
    很容易想到,\(n\)个8可以转换为\((10^{n+1}-1)/9*8\)容易你个集贸啊,xzz推10分钟我推了一个上午顺便膜拜xzz然后就是推式子了。。。(悲\[(10^{n+1}-1)/9*8\equiv0\pmodh\\=>{10^{n+1}*8-8\above1pt9}\equiv0\pmodh\\=>10^{n+1}*8-8\equiv0\pmod{9h}\\=>10^{n+1}*8\e......
  • F - Subsequence LCM
    F-SubsequenceLCMProblemStatementYouaregivenasequenceofpositiveintegers$A=(A_1,A_2,\dots,A_N)$oflength$N$andapositiveinteger$M$.Findthenumber,modulo$998244353$,ofnon-emptyandnotnecessarilycontiguoussubsequencesof$A$suc......
  • [491] Non-decreasing Subsequences
    算法助手用户:这个题目有什么好的思路吗?“Givenanintegerarraynums,returnallthedifferentpossiblenon-decreasingsubsequencesofthegivenarraywithatleasttwoelements.Youmayreturntheanswerinanyorder.”我的代码是这样的:/**@lcapp=leetcod......
  • 单测 填充测试pojo工具类
    直接上importcn.hutool.core.date.DateTime;importcn.hutool.core.util.RandomUtil;importcn.hutool.core.util.ReflectUtil;importcom.google.common.collect.Lists;importlombok.extern.slf4j.Slf4j;importjava.lang.reflect.*;importjava.util.*;/***des......
  • [POJ2891]Strange Way to Express Integers公式推导
    没啥事干,想着推个式子玩玩。题目链接题意不过多赘述,直接上过程:由题意得\[\begin{cases}x\equiva_1\,(mod\,\,n_1)\\x\equiva_2\,(mod\,\,n_2)\end{cases}\]展开得\[x=k_1·n_1+a_1=k_2·n_2+a_2\dots①\]移项得\[k_1·n_1=(a_2-a_1)+k_2·n_2\]\[k_1·n......