Problem
N个整数组成的序列a[1],a[2],a[3],…,a[n],从中选出一个子段(a[i],a[i+1],…a[j]),使这个子段的和>0,并且这个和是所有和>0的子序列中最小的。
例如:4,-1,5,-2,-1,2,6,-2。-1,5,-2,-1,序列和为1,是最小的。
Solution
求前缀和,用map存每个数出现的最小最大坐标,去重,相邻两个能组成的话,差取最小,注意加入0。
解释一下为什么只需检查相邻2个数就可以,设ABC是排序后的结果,如果A同B不能组成序列,而A同C可以组成序列,那么B同C也可以组成序列,并且BC会是一个更优的解。
%一下远古巨佬
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
| #include<iostream> #include<stdio.h> #include<algorithm> #include<map> #include<queue> #include<cstring> #include<stack> #define mod 998244353LL #define mem(ss) memset(ss,0,sizeof(ss)) typedef long long ll; typedef long double ld; #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} inline int read(){int data=0;char ch=0;while (ch<'0' || ch>'9') ch=getchar();while (ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data;} ll lowspeed(ll a,ll b,ll p){ll cur=a,ans=0;while(b){if(b&1) ans=(ans+cur)%p;cur=(cur+cur)%p;b>>=1;}return ans%p;} ll speed(ll a,ll b,ll p){ll cur=a,ans=1;while(b){if(b&1) ans=lowspeed(ans,cur,p)%p;cur=lowspeed(cur,cur,p)%p;b>>=1;}return ans%p;} int n; ll a[50020]; ll ans=1e15; map<int,int>mx; map<int,int>mn; int main(){ io_opt; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; a[i]+=a[i-1]; }
for(int i=0;i<=n;i++){ if(!mn[a[i]]){ mn[a[i]]=i; } mx[a[i]]=i; }sort(a,a+1+n); ll m=unique(a,a+1+n)-(a+1);
for(int i=0;i<m;i++){ if(mn[a[i]]<mx[a[i+1]]){ ans=min(ans,a[i+1]-a[i]); }
} if(ans==1e15){ cout<<"0"<<endl; } else{ cout<<ans<<endl; } return 0; }
|