洛谷P5098 洞穴里的牛之三

贪心，可以用分类讨论的方法，可以得出如果\(n^2\)枚举则会过不了，而我们观察原题中的式子,有: \(∣x1−x2∣+∣y1−y2∣\)

发现式子中的绝对值很恶心，而考虑如果没有绝对值的话会有四种情况。

\((x1-x2)+(y1-y2)=x1+y1-(x2+y2)\)
\((x1-x2)-(y1-y2)=x1-y1-(x2-y2)\)
\(-(x1-x2)+(y1-y2)=x2-y2-(x1-y1)\)
\(-(x1-x2)-(y1-y2)=x2+y2-(x1+y1)\)

可以发现x2,y2与x1,y1之间是可以相互转化的，即(x1,y1)与(x2,y2)的组合如果枚举的话会枚举两次，因此其实简化一下，则可以发现只有1、2两种情况。

因此直接排序贪心，分类讨论求最大值即可。

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <cstring>

#define N 1010003

using namespace std;

struct asd {

    int x, y, ans1, ans2;

}data[N];

bool cmp1(asd a, asd b) {return a.ans1 < b.ans1;}

bool cmp2(asd a, asd b) {return a.ans2 < b.ans2;}

int n, ans;

int main()

{

    scanf("%d", &n);

    for (register int i = 1; i <= n; i++)

        scanf("%d%d", &data[i].x, &data[i].y), data[i].ans1 = data[i].x + data[i].y, data[i].ans2 = data[i].x - data[i].y;

    sort(data + 1, data + 1 + n, cmp1);

    ans = max(ans, data[n].ans1 - data[1].ans1);

    sort(data + 1, data + 1 + n, cmp2);

    ans = max(ans, data[n].ans2 - data[1].ans2);

    printf("%d", ans);

    return 0;

}

巴特西

洛谷P5098 洞穴里的牛之三

最新文章

热门文章