51Nod 1065 最小正子段和

题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1065

题意:略。

思路:求一下前缀和,然后排个序,判断相邻两个位置是否合法再更新答案就好了。因为如果相近的位置上的node满足其pos的前后关系,就比较最小值,因为是相近的,所以已经是最小值的可能值了,其余的绝对不可能了,假设A到B不能形成队列,A到C形成队列了,那么B到C一定是比A到C的数值更小,而且还一定能够形成队列(A与B不能形成队列,说明posA>posB,A与C能形成队列,说明posA<posC,那就一定有posB<posC)。

P.S:排序的时候如果前缀和相等要把位置大的放前面,尽量让满足>0的位置满足要求。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define MOD 1e9+7
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=50000+5;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);}
template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;}
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
struct Node{
    ll num;
    int id;
    bool operator<(const Node&b)const{
        if (num==b.num) return id>b.id;
        return num<b.num;
    }
}a[maxn];
int n;
void init(){}
int main(){
    read(n);
    ll sum=0,x,ans;
    a[0].id=a[0].num=0;
    for (int i=1;i<=n;i++){
        read(x);
        sum+=x;
        a[i].num=sum;
        a[i].id=i;
    }
    sort(a,a+1+n);
    bool flag=false;
    for (int i=n;i>=1;i--){
        if (a[i].id>a[i-1].id && a[i].num-a[i-1].num>0){
            if (!flag){
                ans=a[i].num-a[i-1].num;
                flag=true;
            }
            else ans=min(ans,a[i].num-a[i-1].num);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注