Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:为什么wa?我先求前n个数和,把这些和排序。然后用两个指针i,j,从前往后找。请帮忙。

Posted by x1uc at 2022-04-27 19:21:16 on Problem 2566
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator