讨论 / 坑爹
bf109 2013-03-25 21:26:00
点我顶贴 收藏 删除
此题其实是坑爹的

想多你就输了

/* RQNOJ P690 */

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <algorithm>

using namespace std;

typedef struct node1

{

long long val;

int L;

}T;

int n;

T a[1000001];

int cmp(T a,T b)

{

if (a.val==b.val)return a.L>b.L;

return a.val<b.val;

}

void init()

{

cin>>n;

for (int i=1;i<=n;i++)scanf("%I64d",&a[i].val),a[i].val+=a[i-1].val, a[i].L=i;

sort(a,a+1+n,cmp);

}

void work()

{

long long t,ans=1000000000000000LL,mv=a[0].val;int L,R,ml=0;

for (int i=1;i<=n;i++)

{

if (a[i].val != a[i-1].val)ml=a[i-1].L,mv=a[i-1].val;

t=a[i].val-mv;

if (t>0 && t<ans)

ans=t,R=a[i].L,L=ml;

else if (t==ans){

if (ml<L)L=ml,R=a[i].L;

else if (ml==L && a[i].L<R)R=a[i].L;

}

}

cout<<ans<<" "<<L+1<<" "<<R;

}

int main(void)

{

init();

work();

system("PAUSE");

return 0;

}

查看更多回复
提交回复