题目
一整数数列a1, a2, ... , an(有正有负),以及另一个整数k,求一个区间[i, j],(1 <= i <= j <= n),使得a[i] + ... + a[j] = k。
思路
前缀和+n方查找,1e8如果数据小也是可以过的,毕竟1级题,也可以求前缀和,对前缀和排序,枚举i位置,二分查找j位置。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| #include<bits/stdc++.h> #define ll long long #define db double using namespace std; ll a[10020],sum[10020]; ll n,k; int main(){ scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; } for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ if(sum[j]-sum[i-1]==k){ printf("%d %d\n",i,j); return 0; } } } cout<<"No Solution\n"; return 0; }
|