记录一下自己的笔试的代码题

第一题

给出n个点，寻找两个点之间的最短距离是多少，并保留4位小数。


    //两点间距离
    int point(){
        int n;
        cin>>n;
        if(n == 1){
            cout<<fixed<<setprecision(4)<<0.0;
            return 0;
        }
        vector<int> x(n), y(n);
        for(int i = 0; i < n; ++i){
            cin>>x[i];
        }
        for(int i = 0; i < n; ++i){
            cin>>y[i];
        }
        double mindist = (double)INT32_MAX;
        for(int i = 0; i < n; ++i){
            for(int j = i+1; j < n; ++j){
                double dist = sqrt((double)((y[i] - y[j]) * (y[i] - y[j]) + (x[i]-x[j]) * (x[i]-x[j])));
                if(mindist - dist > 0.000001) mindist = dist;
            }
        }
        cout<<fixed<<setprecision(4)<<mindist;
        return 0;
    }

暴力解法，时间复杂度n*(n-1)/2，O(n²)，全通过。

第二题

给出N段绳子，切成K段能切出最长是多少。


    //切绳子K段
    int cut(){
        int N, K;
        cin>>N>>K;
        vector<int> v(N);
        int sum = 0;
        for(int i = 0; i < N; ++i){
            double t;
            cin>>t;
            v[i] = (int)(t * 100);
            sum += v[i];
        }
        if(N == 1){
            cout<<fixed<<setprecision(2)<<(double)v[0]/ (double)K / 100.0;
            return 0;
        }
        int l = sum / K;
        int cnt = 0;
        while(cnt < K){
            cnt = 0;
            for(int n : v){
                cnt += n / l;
            }
            if(cnt >= K) break;
            else l -= K-cnt;
        }
        cout<<fixed<<setprecision(2)<<(double)l/100.0;
        return 0;
    }

为了减少浮点运算，先将有两位小数的绳子长度乘100。首先求出总和能切出的最大绳子长度，再统计每条绳子能切出这个长度多少条。每次使长度减少两者差值，直到切出来的长度大于或等于K为止。全通过。