51Nod 和为k的连续区间

╰半夏微凉° 2021-09-29 08:40 268阅读 0赞

一整数数列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 10
    1
    2
    3
    4
    5
    6

Output示例

1 4
    数据小时，可以暴力，效率比较高的是用map储存前缀和的位置

#include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    #include <vector>
    #include <queue>
    #include <stack>
    #include <cstdlib>
    #include <iomanip>
    #include <cmath>
    #include <cassert>
    #include <ctime>
    #include <map>
    #include <set>
    using namespace std;
    #pragma comment(linker, "/stck:1024000000,1024000000")
    #define lowbit(x) (x&(-x))
    #define max(x,y) (x>=y?x:y)
    #define min(x,y) (x<=y?x:y)
    #define MAX 100000000000000000
    #define MOD 1000000007
    #define pi acos(-1.0)
    #define ei exp(1)
    #define PI 3.1415926535897932384626433832
    #define ios() ios::sync_with_stdio(true)
    #define INF 0x3f3f3f3f
    #define mem(a) ((a,0,sizeof(a)))
    typedef long long ll;
    ll a[10006]={
        0},n,k;
    map<ll,int>m;
    int main()
    {
        scanf("%lld%lld",&n,&k);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            a[i]+=a[i-1];
        }
        for(int i=n;i;i--)
            m[a[i]]=i;
        int flag=0,l,r;
        for(int i=1;i<=n;i++)
        {
            if(a[i]-k==0 || m[a[i]-k])
            {
                if(!flag && m[a[i]-k]+1<=i) {l=m[a[i]-k]+1;r=i;flag^=1;}
                else if(flag && m[a[i]-k]+1<=i)
                {
                    if(m[a[i]-k]+1<l) {l=m[a[i]-k]+1;r=i;}
                    else if(m[a[i]-k]+1==l) r=min(r,i);
                }
            }
        }
        if(!flag) printf("No Solution\n");
        else printf("%d %d\n",l,r);
        return 0;
    }

转载于:https://www.cnblogs.com/shinianhuanniyijuhaojiubujian/p/8955301.html