1 条题解

  • 3
    @ 2021-6-13 19:39:46

    Subtask 1\texttt{Subtask 1}

    暴力即可,时间复杂度 O(n2)O(n^2)

    Subtask 2\texttt{Subtask 2}

    可以使用稀疏表或者一些其他排序后再求解的方法,时间复杂度 O(nlogn)O(n\text{log}n)

    Subtask 3\texttt{Subtask 3}

    时间复杂度 O(n)O(n)

    考虑将每个二元组的 Y\texttt{Y} 轴坐标取其绝对值,然后将二元组按照 X\texttt{X} 坐标递增的顺序进行排列,则两个二元组之间的变异距离可以看成以二元组 X\texttt{X} 坐标之间的线段和第一个二元组组 Y\texttt{Y} 轴坐标所形成的线段、第二个二元组 Y\texttt{Y} 轴坐标所形成的线段围成的矩形的面积。不过,此矩形的侧边长度是两个二元组 Y\texttt{Y} 坐标绝对值中的较小值。

    根据木桶原理,一个木桶所能装的水的容量只由高度最短的那块木板的决定,而此题中,矩形的面积只由高度较短的线段决定。因此可以考虑用双指针从首尾往中间扫描,在扫描过程中,只移动较短线段的指针,因为矩形的面积取决于较短的线段,只有在改变较短线段的时候才有可能产生新的最大值。

    参考代码:

    #include <bits/stdc++.h>
    
    using namespace std;
    
    const int MAXN = 2000010;
    
    const int LENGTH = (1 << 20);
    
    inline int nextChar()
    {
        static char buffer[LENGTH], *p = buffer, *end = buffer;
        if (p == end) {
            if ((end = buffer + fread(buffer, 1, LENGTH, stdin)) == buffer) return EOF;
            p = buffer;
        }
        return *p++;
    }
    
    inline bool nextInt(int &x)
    {
        static char negative = 0, c = nextChar();
        negative = 0, x = 0;
        while ((c < '0' || c > '9') && c != '-')
        { if (c == EOF) return false; c = nextChar(); }
        if (c == '-') { negative = 1; c = nextChar(); }
        do x = (x << 3) + (x << 1) + c - '0'; while ((c = nextChar()) >= '0');
        if (negative) x = -x;
        return true;
    }
    
    int ps[MAXN];
    
    int main(int argc, char *argv[])
    {
        cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
        
        int T, n;
        nextInt(T);
        for (int cs = 1; cs <= T; cs++)
        {
            nextInt(n);
            memset(ps, 0, sizeof ps);
            int bias = 1000000;
            for (int i = 0, x, y; i < n; i++)
            {
                nextInt(x);
                nextInt(y);
                ps[x + bias] = max(ps[x + bias], abs(y));
            }
            int low = 0, high = MAXN - 1;
            long long D = 0;
            while (low < high)
            {
                D = max(D, 1LL * abs(low - high) * min(ps[low], ps[high]));
                if (ps[low] <= ps[high]) low++;
                else high--;
            }
            cout << D << '\n';
        }
        return 0;
    }
    
    • 1

    信息

    ID
    144
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    53
    已通过
    8
    上传者