luoguU42592

20分思路

对给出的序列求出前缀和,然后\(n^2\)暴力枚举即可拿到第一档分

40分思路

对于数列中的数都相同的情况。只需要特判即可。只要特别注意全都是0的情况即可。

100分思路

仔细考虑一下题目意思就可以知道,其实这个题就是求出前缀和之后,对于每个位置上的数,在前面的所有数中找一个与它差值最小的数。也就是找比他大的最小的数和比他小的最大的书。考虑到二分,可惜前面的数没有单调性。然后跟随某某某快乐的写起了set,然后t到飞起。

重新再考虑这个题,其实没有必要非得在前面找与他差值最小的数,可以是在全部的数中寻找,因为如果后面有差值更小的,肯定会把前面的覆盖掉。所以考虑到sort一边,然后只要记录下相邻的两个数差值更小的那个即可。对于差值相同的,再去比较区间长度就可以了。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1000000+100,INF=1e19+100;
ll read() {
    ll x=0,f=1; char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    ll x,pos;
}a[N];
ll ab(ll x) {
    return x<0?-x:x;
}
bool cmp (node x,node y) {
    return x.x==y.x?x.pos<y.pos:x.x<y.x;
}
ll b[N];
int main() {
    int n=read();
    int bz=1;
    for(int i=1;i<=n;++i) {
        b[i]=read();
        if(b[i]!=b[i-1]&&i>1) bz=0;
        a[i].x=b[i]+a[i-1].x;
        a[i].pos=i;
    }
    if(bz==1) {
        if(b[1]==0) printf("0\n%lld",n);
        else printf("%lld\n1",ab(b[1]));
        return 0;
    }
    sort(a,a+n+1,cmp);
    int now=0;
    ll ans=INF,pos=0;
    for(int i=1;i<=n;++i) {
        if(ab(a[i].x-a[now].x)<ans) {
            pos=ab(a[i].pos-a[now].pos);
            ans=ab(a[i].x-a[now].x);
        }
        else if(ab(a[i].x-a[now].x)==ans&&ab(a[i].pos-a[now].pos)>pos)
            pos=ab(a[i].pos-a[now].pos);
        if(a[i].x!=a[i-1].x)
            now=i;
    }
    cout<<ans<<"\n"<<pos;
    return 0;
}