51nod1065 最小正子段和
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<set> using namespace std; typedef long long ll; ll a[50010]; struct node { ll sum,no; }; node s[50010],t[50010]; bool cmp(node aa,node bb) { if(aa.sum==bb.sum) return aa.no<bb.no; return aa.sum<bb.sum; } int main() { // freopen("out.txt","w",stdout); int n; ll ans=99999999999999; scanf("%d",&n); for(int i = 1; i <= n; ++i) { scanf("%lld",&a[i]); s[i].sum=a[i]+s[i-1].sum; s[i].no=i; } s[0].sum=0; s[0].no=0; sort(s,s+n+1,cmp); int o = 0; for(int i = 0; i <= n; ++i) { if(s[i].sum!=s[i-1].sum) { t[o].sum=s[i].sum; t[o++].no=s[i].no; } } for(int i = 1; i <= o; ++i) { if(t[i-1].no<t[i].no) { ans=min(ans,t[i].sum-t[i-1].sum); } } cout<<ans<<endl; return 0; }夹克爷的解答链接
按照前n项和大小排序，将相同的项合并 那么答案一定是相邻的两个 设ABC是排序后的结果，如果A同B不能组成序列，而A同C可以组成序列，那么B同C也可以组成序列，并且BC会是一个更优的解。
