Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:为什么wa?我先求前n个数和,把这些和排序。然后用两个指针i,j,从前往后找。请帮忙。In Reply To:为什么wa?我先求前n个数和,把这些和排序。然后用两个指针i,j,从前往后找。请帮忙。 Posted by:tengshengbo at 2005-08-15 17:50:42 > #include <cstdio> > #include <algorithm> > #include <iostream> > using namespace std; > struct node > { > long long n; > int c; > }s[100005]; > bool pr(struct node const a,struct node const b) > { > if(a.n>b.n) return 0; > return 1; > } > long long ab(long long h) > { > if(h>=0) return h; > return -h; > } > int main() > { > int n,k; > scanf("%d%d",&n,&k); > while(n>0) > { > int i,j; > scanf("%I64d",&s[0].n); > s[0].c=1; > for(i=1;i<n;i++) > { > long long temp; > scanf("%I64d",&temp); > s[i].n=s[i-1].n+temp; > s[i].c=i+1; > } > s[n].n=0; > s[n].c=0; > sort(s,s+n+1,pr); > /* for(i=0;i<n;i++) > { > cout<<s[i].n<<" "<<s[i].c<<endl; > } */ > int p; > for(p=0;p<k;p++) > { > long long y; > scanf("%I64d",&y); > /*if(s[0].n==y) > { > cout<<y<<" "<<"1"<<" "<<n<<endl; > continue; > } */ > i=0; > j=1; > int si,sj,most; > si=s[0].c; > sj=s[1].c; > most=s[1].n-s[0].n; > while(1) > { > // > //system("pause"); > if(i==j) j++; > // cout<<i<<" "<<s[i].n<<" "<<j<<" "<<s[j].n<<endl; > // system("pause"); > if(s[j].n-s[i].n>y) > { > if((s[j].n-s[i].n-y)<ab(y-most)) > { > most=s[j].n-s[i].n; > sj=s[j].c; > si=s[i].c; > } > i++; > //if(i==n) break; > } > else if(s[j].n-s[i].n<y) > { > if((y-(s[j].n-s[i].n))<ab(y-most)) > { > most=s[j].n-s[i].n; > sj=s[j].c; > si=s[i].c; > } > j++; > if(j>n) break; > } > else > { > most=y; > sj=s[j].c; > si=s[i].c; > break; > } > } > if(sj>si) > cout<<most<<" "<<si+1<<" "<<sj<<endl; > else cout<<most<<" "<<sj+1<<" "<<si<<endl; > } > scanf("%d%d",&n,&k); > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator