| ||||||||||
| 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