题目描述

如有hack数据，请给出

算法1

(暴力枚举) $O(n^2logn)$

C++ 代码

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e3+10;
int n,js=0,a[N];
struct dui{
    int l,r,num;
}d[N*N];
bool cmp(dui x,dui y){
    return x.num<y.num;
}
int check(int x,int y,int a,int b){
    if((x>=a&&y<=b)||(x<=a&&y>=b))return 0;
    else return 1;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){//我们先通过二层循环，暴力出每一种选法
        int s=0;
        for(int j=i;j<=n;j++){
            s+=a[j];
            d[js].num=s;
            d[js].l=i;
            d[js++].r=j;
        }
    }
    sort(d,d+js,cmp);
    //将他们从小到大排序，力量值之和差距最小的一定是相邻的两种选法
    //不用管区间选择重叠的情况，重叠部分相当于两种选法都没选重叠部分
    //将区间包含的跳过
    int ans=1e12+10;
    for(int i=1;i<js;i++)
        if(check(d[i].l,d[i].r,d[i-1].l,d[i-1].r))
            ans=min(ans,d[i].num-d[i-1].num);
    cout<<ans;
    return 0;
}