题解

134 条题解

  • 5
    @ 2016-08-14 13:46:49
    /*
    我去,这题恶心啊。
    基本思路,从小到大快排,然后对于每个a[i],除以个黄金比例可以得出一个正好完美的数,
    再用这个数去二分查找数列中找最近的数,再用找到这个数去除以a[i],
    得出的比例要与黄金比例最接近。
    1.精度问题:黄金比例一定要直接按题目的来。不要就保留前几位orz
    2.查找问题:可能是我太弱了,一直错在查找这个地方。二分查找返回下标。
    这个下标到底选哪个好呢?又不是找相等+浮点数
    这就比较尴尬了,然后弱逼的我是一开始直接返回l-1,结果呵呵哒一直有一个点过不去呀,
    然后我就l,l-1,l+1三个比较一遍取最优的返回,结果就特么过了?
    发现自己还是太不细心加做题少啊,弱逼一枚
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    using namespace std;
    
    const double xyz=0.6180339887498949;
    int n;
    double a[30005];
    double ans=9999999999.0;
    int x,y;
    
    int search(double e,int p)
    {
        int l=p+1,r=n;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(a[mid]<=e)
                l=mid+1;
            else r=mid-1;
        }
        double w=fabs(a[l]-e);
        double b=fabs(a[l-1]-e);
        double c=fabs(a[l+1]-e);
        if(w<b&&w<c)
            return l;
        else if(b<w&&b<c)
            return l-1;
        else return l+1;
    }
    
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++)
        {
            double t=(a[i]/(xyz));
            int k=search(t,i);
            double temp=fabs(a[i]/a[k]-xyz);
            if(temp<ans)
            {
                ans=temp;
                x=a[i];
                y=a[k];
            }
        }
        cout<<x<<endl<<y<<endl;
        return 0;
    }
    
  • 3
    @ 2017-08-29 19:20:53

    Accepted

    状态 耗时 内存占用

    #1 Accepted 1ms 256.0 KiB
    #2 Accepted 1ms 256.0 KiB
    #3 Accepted 24ms 372.0 KiB
    #4 Accepted 27ms 328.0 KiB
    #5 Accepted 24ms 388.0 KiB
    #6 Accepted 27ms 196.0 KiB
    #7 Accepted 29ms 360.0 KiB
    #8 Accepted 23ms 256.0 KiB
    #9 Accepted 23ms 256.0 KiB
    #10 Accepted 26ms 324.0 KiB
    代码
    const p=0.6180339887498949;
    var
    a:array[0..30001]of longint;
    n,i,x,y:longint;
    min:real;
    procedure sort(l,r: longint);
    var
    i,j,x,y: longint;
    begin
    i:=l;
    j:=r;
    x:=a[(l+r) div 2];
    repeat
    while a[i]<x do
    inc(i);
    while x<a[j] do
    dec(j);
    if not(i>j) then
    begin
    y:=a[i];
    a[i]:=a[j];
    a[j]:=y;
    inc(i);
    j:=j-1;
    end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
    end;
    procedure search(l,r:longint);
    var
    m:longint;
    k:real;
    begin
    m:=a[(l+r) div 2];
    k:=abs(a[i]/m-p);
    if k<min then begin min:=k; x:=a[i]; y:=m; end;
    if l>=r then exit;
    if r-l=1 then begin
    if abs(a[i]/a[r]-p)<min then begin min:=abs(a[i]/a[r]-p); x:=a[i]; y:=a[r]; end;
    exit;
    end;
    if a[i]/m<p then search(l,(l+r) div 2);
    if a[i]/m>p then search((l+r) div 2,r);
    end;
    begin
    readln(n);
    for i:=1 to n do
    read(a[i]);
    readln;
    sort(1,n);
    min:=maxlongint;
    for i:=1 to n-1 do
    search(i+1,n);
    writeln(x);
    writeln(y);
    end.

  • 3
    @ 2016-04-04 09:42:09
    uses math;
    const p=0.6180339887498949;
    var a:array[0..30001] of longint;
      w:array[1..2] of longint;
      n,i:longint;
    
    procedure qsort(b,e:longint);
    var temp,x,i,j:longint;
    begin
      if b<e then begin
        x:=random(e-b)+b;
        temp:=a[x];a[x]:=a[e];a[e]:=temp;
    
        x:=a[e];i:=b-1;
        for j:=b to e-1 do
          if a[j]<x then begin
            inc(i);
            temp:=a[j];a[j]:=a[i];a[i]:=temp;
          end;
        a[e]:=a[i+1];a[i+1]:=x;
    
        qsort(b,i);
        qsort(i+2,e);
      end;
    end;
    
    procedure bin(i:longint);
    var lb,ub,mid:longint;k:extended;
    begin
      lb:=i;ub:=n+1;
      k:=a[i]/p;
      while (ub-lb)>1 do begin
        mid:=(lb+ub) div 2;
        if a[mid]>=k then ub:=mid
        else lb:=mid;
      end;
      if (ub<n+1) and (abs(a[i]/a[ub]-p)<abs(w[1]/w[2]-p)) then begin
        w[1]:=a[i];
        w[2]:=a[ub];
      end;
      if (lb>i) and (abs(a[i]/a[lb]-p)<abs(w[1]/w[2]-p)) then begin
        w[1]:=a[i];
        w[2]:=a[lb];
      end;
    end;
    
    begin
      randomize;
      read(n);
      for i:=1 to n do read(a[i]);
      qsort(1,n);
      w[1]:=a[1];w[2]:=a[2];
      for i:=1 to n do bin(i);
      writeln(w[1]);
      writeln(w[2]);
    end.
    
  • 2
    @ 2018-04-15 20:22:54

    简单的二分
    手写了一下abs

    #include<iostream>
    #include<algorithm>
    #include<cmath>
    const double N=0.6180339887498949;
    using namespace std;
    int a[30010];
    
    double aabs(double x)
    {
        if(x>0)
         return x;
        return -x;
    }
    
    int main()
    {
        int n,i,l,r,mid,ans,z,y;
        double minn=100000.0,ha;
        cin>>n;
        for(i=1;i<=n;i++)
         cin>>a[i];
        sort(a+1,a+n+1);
        for(i=1;i<n;i++)
         {
            l=i+1;
            r=n;
            while(l<=r)
            {
                mid=(l+r)/2;
                ha=double(a[i])/(double(a[mid]));
                //cout<<l<<" "<<r<<" ";
            //  cout<<ha<<endl;
                if(aabs(ha-N)<aabs(minn-N))
                {
                 minn=ha;
                 z=a[i];
                 y=a[mid];
                }
                if(ha<N)
                 r=mid-1;
                else
                 l=mid+1;
            }
         }
         cout<<z<<endl<<y;
         return 0;
    }
    
  • 2
    @ 2017-08-20 14:32:53

    这个题目告诉我们做题要大胆,只要敢做强制类型转换也没问题的

    //
    #if 1
    
    //INCLUDE HEADERS
    #include <iostream>
    #include <algorithm>
    #include <string>
    #include <string.h>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <map>
    #include <set>
    #include <list>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <memory.h>
    #include <sstream>
    //MACROS
    #define ll long long
    #define MAX     65535
    #define pause system("pause");
    #define debug printf("__DEBUG__\n");
    using namespace std; 
    
    #define sigma 0.6180339887498949
    
    int main() {
        int n;
        cin >> n;
        vector<double>v;
        int x;
        for (int i = 0; i < n;++i)
        {
            cin >> x;
            v.push_back(x);
            v.push_back(x*sigma);
        }
        sort(v.begin(), v.end());
    
        int j = 0;
        double min = MAX;
        for (unsigned i = 1; i < v.size();++i)
        {
            if (v[i]-v[i-1]<min)
            {
                if ((int(v[i])==v[i])^(int(v[i-1])==v[i-1]))
                {
                    min = v[i] - v[i - 1];
                    j = i;
                }
            }
        }
        if (int(v[j])==v[j])
        {
            cout << v[j]  <<endl << int(v[j - 1] / sigma) << endl;
        }
        else {
            cout << v[j - 1] << endl << int(v[j] / sigma) << endl;
        }
    
    
        return 0;
    }
    
    #endif
    
    
  • 2
    @ 2016-09-24 09:48:12

    写了个奇奇怪怪的东西233
    把所有长度和0.618倍长度一起排序,距离最近的就是答案
    不加1e-10得90,加了终于ac

    
    #include<iostream>
    #include<stdlib.h>
    #include<stdio.h>
    #include<string.h>
    #include<limits.h>
    #include<math.h>
    #include<algorithm>
    #include<string>
    #include<queue>
    #include<vector>
    #include<map>
    #include<set>
    #include<bitset>
    #include<iomanip>
    using namespace std;
    
    long double g=0.6180339887498949;
    inline long double myabs(long double x){return((x>0.0)?x:-x);}
    inline bool eq(long double x,long double y){return((myabs(x-y)<1e-8)?1:0);}
    inline int sgn(long double x){if(!eq(x,0.0)){if(x>0) return 1;else return -1;} else return 0;}
    int comp0(const void *a,const void *b){return sgn(((double)(((long double *)a)[0])-(double)(((long double *)b)[0])));}
    
    int main_wa() {
     int n,t=0,c=0;cin>>n;long double l[2*n+2][2];int lb[n+1];
        for(int i=0;i<n;i++){cin>>lb[i+1];if(lb[i+1]){l[t][0]=lb[i+1];l[t][1]=i+1;t++;l[t][0]=l[t-1][0]*g;l[t][1]=-l[t-1][1];t++;}}
        if(!t){cout<<0<<endl<<0<<endl;return 0;}
        if(t==2){cout<<0<<endl<<l[0][0]<<endl;return 0;}
        qsort(l,t,2*sizeof(long double),comp0);
        long double min=1e6;long long int ia=1e6,ib=1e6;
        for(int i=1;i<t;i++)
        {
    
            if((((myabs(l[i][0]-l[i-1][0])/l[i-1][0])<min)||(eq((myabs(l[i][0]-l[i-1][0])/l[i-1][0]),min)&&(myabs(l[i][0]*l[i-1][0])<lb[ia]*lb[ib]*g)))&&(!eq(l[i][1]+l[i-1][1],0.0))&&(l[i][1]*l[i-1][1]<0))
            {min=(myabs(l[i][0]-l[i-1][0])/l[i-1][0]);ia=myabs(l[i][1])+1e-6;ib=myabs(l[i-1][1])+1e-6;
            if(lb[ia]>lb[ib]) {c=ia;ia=ib;ib=c;}}
    
        }cout<<lb[ia]<<endl<<lb[ib]<<endl;
    
        return 0;
    }
    
    int main() {
     int n,t=0,c=0;cin>>n;long double l[2*n+2][2];int lb[n+1];
        for(int i=0;i<n;i++){cin>>lb[i+1];if(lb[i+1]){l[t][0]=lb[i+1];l[t][1]=i+1;t++;l[t][0]=l[t-1][0]*g;l[t][1]=-l[t-1][1];t++;}}
        if(!t){cout<<0<<endl<<0<<endl;return 0;}
        if(t==2){cout<<0<<endl<<l[0][0]<<endl;return 0;}
        qsort(l,t,2*sizeof(long double),comp0);
        long double min=1e6;long long int ia=1e6,ib=1e6;
        for(int i=1;i<t;i++)
        {
    
            if((((myabs(l[i][0]-l[i-1][0])/l[i-1][0])+jd<min)||(eq((myabs(l[i][0]-l[i-1][0])/l[i-1][0]),min)&&(myabs(l[i][0]*l[i-1][0])<lb[ia]*lb[ib]*g)))&&(!eq(l[i][1]+l[i-1][1],0.0))&&(l[i][1]*l[i-1][1]<0))
            {min=(myabs(l[i][0]-l[i-1][0])/l[i-1][0]);ia=myabs(l[i][1])+1e-6;ib=myabs(l[i-1][1])+1e-6;
            if(lb[ia]>lb[ib]) {c=ia;ia=ib;ib=c;}}
    
        }cout<<lb[ia]<<endl<<lb[ib]<<endl;
    
        return 0;
    }
    
    
    

    真是怀念啊...


    现在还有两个月高考之际,回顾我高一时写的惨不忍睹的码(虽然之后去搞ChO然后Cu了)


    大一打卡。
    作为竞赛生的日子...真好啊。

  • 2
    @ 2006-10-09 11:13:56

    C++模版库就是好用!

    ......

    for(set::iterator i=s.begin(); i!=s.end(); i++)

    {

    x=s.lower_bound(int((*i)*0.618));

    ......

    }

    ......

  • 2
    @ 2006-10-03 21:22:29

    晕……

    不处理误差得90分

    误差定成1e-6得20分

    误差定成1e-10就AC了

    比赛时误差定成1e-6了……倒霉

  • 1
    @ 2021-02-27 11:03:39

    //
    #if 1

    //INCLUDE HEADERS
    #include <iostream>
    #include <algorithm>
    #include <string>
    #include <string.h>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <map>
    #include <set>
    #include <list>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <memory.h>
    #include <sstream>
    //MACROS
    #define ll long long
    #define MAX 65535
    #define pause system("pause");
    #define debug printf("__DEBUG__\n");
    using namespace std;

    #define sigma 0.6180339887498949

    int main() {
    int n;
    cin >> n;
    vector<double>v;
    int x;
    for (int i = 0; i < n;++i)
    {
    cin >> x;
    v.push_back(x);
    v.push_back(x*sigma);
    }
    sort(v.begin(), v.end());

    int j = 0;
    double min = MAX;
    for (unsigned i = 1; i < v.size();++i)
    {
    if (v[i]-v[i-1]<min)
    {
    if ((int(v[i])==v[i])^(int(v[i-1])==v[i-1]))
    {
    min = v[i] - v[i - 1];
    j = i;
    }
    }
    }
    if (int(v[j])==v[j])
    {
    cout << v[j] <<endl << int(v[j - 1] / sigma) << endl;
    }
    else {
    cout << v[j - 1] << endl << int(v[j] / sigma) << endl;
    }

    return 0;
    }

    #endif

  • 1
    @ 2019-03-03 16:20:40

    我的思路:左边的数从i开始,右边的数从i+1到n-1结束。然后二分搜索右边的数。
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n,base,mid,right1,left1,saveleft,saveright,flag,add=70000;
    double stand =0.6180339887498949,temp,dis;
    int data[40000]={0};
    double divv2=10000000;
    int myabs(double divv)
    {
    if(divv <stand)
    {
    return -1;
    }
    else return 1;
    }
    double myabs2(double divv)
    {
    if(divv>stand) return divv-stand;
    else return stand -divv;
    }
    int main()
    {
    cin>>n;
    for(int i=0;i<n;i++) cin >>data[i];
    sort(data,data+n);
    for(int i=0;i+1<n;i++)
    {
    base=i;
    left1=i+1;
    right1=n-1;
    mid=(left1+right1) >>1; //得到了位置
    while(left1<=right1)
    {
    dis=(double)data[base] / data[mid];
    dis=myabs2(dis);
    if(dis<divv2)
    {
    //cout <<data[base]<<" " <<data[mid] <<endl;
    divv2=dis;
    saveleft=base,saveright=mid;
    }
    flag =myabs((double)data[base]/data[mid]);
    if(flag==-1)
    {
    right1=mid-1;
    }
    else
    {
    left1=mid+1;
    }
    mid=(left1+right1) >>1;

    }
    }
    cout <<data[saveleft]<<endl << data[saveright];
    return 0;
    }

  • 1
    @ 2017-07-18 14:53:07

    说真的,这题没什么难度,没用二分照样过了……思路是先排一遍序;再把每个数乘黄金比的值算出来,最后找2个差最小的数,输出,结束
    ```cpp
    //#include "stdafx.h"
    #include<bits/stdc++.h>
    using namespace std;
    const double golden = 0.6180339887498949;
    int n, x[30009],f,s;
    double goal[30009],minn=100000.000000000000000;

    int main()
    {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++)
    cin >> x[i];
    sort(x, x + n);
    for (int i = 0; i < n; i++)
    {
    goal[i] = double(x[i])*golden;

    }for(int i=0;i<n;i++){
    for(int j=i-1;j>=0;j--)
    if (abs(double(x[j] )- goal[i])< minn)
    {
    minn = abs(double(x[j])- goal[i]);
    f = x[i];
    s = x[j];
    }}
    cout << s <<endl<< f;
    //system("pause");
    return 0;
    }
    ```

    • @ 2017-08-19 10:59:18

      一开始的数据不就是有序的么

  • 1
    @ 2016-11-08 20:44:51

    为何我会RE。。。。help

    #include <stdio.h>

    void Qsort (long l,long r,long s[]);
    double analys(long ,long );
    void Swap(long *a,long *b);
    int main()
    {
    int N,n=0,m=0;
    long a,b;
    double tmp,min=10,P=0.6180339887498949;
    long input[30000];
    scanf("%d",&N);
    for (n=0;n<N;n++)
    scanf("%ld",&input[n]);
    Qsort(0,N-1,input);
    while (input[n]==0) n++;
    for (n=0;n<N-1;n++)
    for (m=n+1;m<N;m++)
    {
    tmp=analys(input[n],input[m]);
    if ((tmp-P)>=0) tmp-=P;
    else tmp=P-tmp;
    if (tmp<min)
    {
    min=tmp;
    a=input[n];
    b=input[m];
    }
    }
    printf("%ld\n%ld\n",a,b);
    return 0;
    }
    double analys(long a,long b)
    {
    return (double)(a/b);
    }
    void Swap(long *a,long *b) //无需添加新变量
    {
    (*a)+=(*b);
    (*b)=(*a)-(*b);
    (*a)-=(*b);
    }
    void Qsort (long l,long r,long s[]) //最终结果为升序数列
    {
    long mid=(l+r)/2,n=l,m=r-1,pivot;
    if ((r-l)==1)
    {
    if (s[r]<s[l]) Swap(&s[l],&s[r]);
    }
    else
    {
    if (s[l]>s[mid]) Swap(&s[l],&s[mid]);
    if (s[l]>s[r]) Swap(&s[l],&s[r]);
    if (s[mid]>s[r]) Swap(&s[r],&s[mid]);
    pivot=s[mid];
    Swap(&s[mid],&s[m]);
    for (;;)
    {
    while (s[++n]<pivot) ;
    while (s[--m]>pivot) ;
    if (n<m) Swap(&s[n],&s[m]);
    else break;
    }
    Swap(&s[n],&s[r-1]);
    Qsort(l,n,s);
    Qsort(n+1,r,s);
    }
    }

  • 0
    @ 2018-07-03 15:09:47

    //我直接用stl中的lower_bound过掉了耶

    #include<bits/stdc++.h>
    #define V (to[i])
    #define debug printf("%d %s\n",__LINE__,__FUNCTION__)
    #define PP system("pause")
    #define N 1000010
    #define NN 2010
    #define NNN 310
    #define eps 1e-18
    
    using namespace std;
    
    namespace program
    {
        #define gc() getchar()
        #define pc putchar
        inline long long read(){
            register long long x=0,f=1;register char c=gc();
            for(;!isdigit(c);c=gc())if(c=='-')f=-1;
            for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
            return x*f;
        }
        inline void write(long long x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);putchar(x%10+'0');}
        inline void writeln(long long x){write(x);puts("");}
        
        int n,id1,id2;
        const long double hjb=0.6180339887498949;
        long double ans=999999999999999.99999999,a[30030];
    
        inline void work()
        {
            n=read();
            for(int i=1;i<=n;i++)
                scanf("%Lf",&a[i]);
            sort(a+1,a+n+1);
            for(int i=1;i<n;i++)
            {
                long double now=a[i]/hjb;
                int oo=lower_bound(a+1,a+n+1,now)-a;
                long double sum1=a[i]/a[oo];
                long double sum2=a[i]/a[oo-1];
                long double sum3=a[i]/a[oo+1];
                if(abs(sum1-hjb)<abs(ans-hjb))
                {
                    ans=sum1;
                    id1=i;
                    id2=oo;
                }
                if(abs(sum2-hjb)<abs(ans-hjb))
                {
                    ans=sum2;
                    id1=i;
                    id2=oo-1;
                }
                if(abs(sum3-hjb)<abs(ans-hjb))
                {
                    ans=sum3;
                    id1=i;
                    id2=oo+1;
                }
            }
            writeln(a[id1]);
            writeln(a[id2]);
        }
    }
    
    int main()
    {
        freopen("gaojunonly1.in","r",stdin);
        program::work();
        return 0;
    }
    
  • 0
    @ 2016-07-24 18:36:31

    有0。。。。。注意了就好了,标记上两个指针,搜就好了

  • 0
    @ 2016-03-26 13:29:49
    /* ***********************************************
    Author        :guanjun
    Created Time  :2016/3/26 10:24:40
    File Name     :vijos1237.cpp
    ************************************************ */
    #include <iostream>
    #include <cstring>
    #include <cstdlib>
    #include <stdio.h>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <map>
    #include <string>
    #include <math.h>
    #include <stdlib.h>
    #include <iomanip>
    #include <list>
    #include <deque>
    #include <stack>
    #define ull unsigned long long
    #define ll long long
    #define mod 90001
    #define INF 0x3f3f3f3f
    #define maxn 30010
    #define cle(a) memset(a,0,sizeof(a))
    const ull inf = 1LL << 61;
    const double eps=0.6180339887498949;
    using namespace std;
    priority_queue<int,vector<int>,greater<int> >pq;
    struct Node{
        int x,y;
    };
    struct cmp{
        bool operator()(Node a,Node b){
            if(a.x==b.x) return a.y> b.y;
            return a.x>b.x;
        }
    };
    
    bool cmp(int a,int b){
        return a>b;
    }
    double a[maxn];
    
    int main()
    {
        #ifndef ONLINE_JUDGE
       // freopen("in.txt","r",stdin);
        #endif
        //freopen("out.txt","w",stdout);
        int n;
        while(cin>>n){
            for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
            sort(a+1,a+n+1);
            double ans=1000000;
            ll ans1,ans2;
            for(int i=1;i<n;i++){
                int y=ceil(a[i]*1.0/eps+0.5);
                int x=lower_bound(a+i+1,a+n+1,y)-a-1;
                double tmp=fabs((double)a[i]/(double)a[x]-eps);
                if(tmp<ans){
                    ans=tmp;
                    ans1=a[i];
                    ans2=a[x];
                }
            }
            cout<<ans1<<endl<<ans2<<endl;
        }
        return 0;
    }
    
    
  • 0
    @ 2016-03-26 13:29:05

    给一组 数据
    5
    100 101 123 123 23466
    输出
    100
    123

  • 0
    @ 2015-12-22 21:40:45

    注意黄金比例一定要取题目里面给的那个数,一位也不要少,我就是少了2位然后wa两次之后第三次才ac的

  • 0
    @ 2015-08-10 21:18:19

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    const double gold = 0.6180339887498949;
    const int MAXN = 1000000;

    int to;
    int num[MAXN];

    int search(int a, int b){
    if(a == b)
    return a;
    int div = (a + b) / 2, flag;
    if(num[div] >= to){
    flag=search(a, div);
    if(abs(num[div+1]-to) < abs(num[flag]-to))
    flag = div + 1;
    }
    else{
    flag=search(div+1, b);
    if(abs(num[div]-to) < abs(num[flag]-to))
    flag = div;
    }
    return flag;
    }

    double fabs(double x){
    if(x >= 0)
    return x;
    else

    return -x;
    }

    int main()
    {
    int n, ans1, ans2;
    double bri = 1000000;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    scanf("%d", &num[i]);
    sort(&num[1], &num[1]+n);

    for(int i=1; i<n; i++){
    to = (int)round(num[i] / gold);
    int u = search(i+1, n);
    double v = fabs( (double)num[i]/(double)num[u] - gold );
    if(v < bri){
    bri = v;
    ans1 = num[i];
    ans2 = num[u];
    }
    }
    printf("%d\n%d\n", ans1, ans2);
    system("pause");
    return 0;
    }
    求指导,,共同进步

  • 0
    @ 2014-01-01 12:00:49

    Vijos 题解:http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
    有疑问请留言 共同进步

  • 0
    @ 2013-11-02 17:41:22

    评测结果
    编译成功

    foo.cpp: In function 'int find(double)':
    foo.cpp:8:12: warning: unused variable 'd' [-Wunused-variable]
    测试数据 #0: Accepted, time = 0 ms, mem = 648 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 648 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 652 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 656 KiB, score = 10
    测试数据 #4: Accepted, time = 31 ms, mem = 652 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 656 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 656 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 656 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 648 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 652 KiB, score = 10
    Accepted, time = 136 ms, mem = 656 KiB, score = 100
    代码
    #include<cstdio>
    #include<algorithm>
    double abs(double a) { if (a>0) return a; else return -a;}
    double min=1,gold=0.6180339887498949;
    int n,l[30010],a,b;
    int find(double flag) {
    int ll=1,rr=n,m;
    double d;
    while (ll+1<rr) {
    m=(ll+rr)/2;
    if (l[m]>=flag) rr=m;
    else ll=m;
    } if (abs(l[ll]-flag)>abs(l[rr]-flag)) return rr;
    else return ll;
    }
    int main(){
    scanf("%d",&n);
    for (int i=1; i<=n; i++) scanf("%d",&l[i]);
    std::sort(l+1,l+1+n);
    for (int i=1; i<=n; i++) {
    int j=find(l[i]/gold);
    double d=l[i];d/=l[j];
    if (abs(d-gold)<min) {
    min=abs(d-gold);
    a=i; b=j;
    }
    } printf("%d\n%d",l[a],l[b]);
    }

信息

ID
1237
难度
7
分类
其他 | 二分查找 点击显示
标签
递交数
5452
已通过
1050
通过率
19%
被复制
17
上传者