首页 > 代码库 > 51nod 1094 和为k的连续区间
51nod 1094 和为k的连续区间
基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题
收藏
关注一整数数列a1, a2, ... , an（有正有负），以及另一个整数k，求一个区间[i, j]，(1 <= i <= j <= n)，使得a[i] + ... + a[j] = k。
Input
第1行：2个数N,K。N为数列的长度。K为需要求的和。(2 <= N <= 10000，-10^9 <= K <= 10^9)第2 - N + 1行：A[i](-10^9 <= A[i] <= 10^9)。
Output
如果没有这样的序列输出No Solution。输出2个数i, j，分别是区间的起始和结束位置。如果存在多个，输出i最小的。如果i相等，输出j最小的。
Input示例
6 10123456
Output示例
1 4
前缀和水过。。
屠龙宝刀点击就送
#include <cstdio>long long sum[55000];int n,k,a[55000];void qr(int &x){ x=0;bool f=1; char ch=getchar(); while(ch>‘9‘||ch<‘0‘) { if(ch==‘-‘) f=0; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+(int)ch-48; ch=getchar(); } x=f?x:(~x)+1;}int main(){ qr(n);qr(k); for(int i=1;i<=n;i++) { qr(a[i]); sum[i]=sum[i-1]+a[i]; if(sum[i]==k) { printf("1 %d",i); return 0; } } int pos=1; while(pos<=n) { int j=pos; while(j<=n) { if(sum[j]-sum[pos-1]==k) { printf("%d %d",pos,j); return 0; } j++; } pos++; } printf("No Solution"); return 0;}
51nod 1094 和为k的连续区间
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。