题解 [USACO2004OPEN]洞穴里的牛之三

这道题目难度不是很大的,主要就是分类讨论。

题目意思

题目意思很简单,就是让你找出一对点对使得两点之间曼哈顿距离最大。

暴力大法

这道题目显然暴力不能过。

正解

这道题目难就难在分类讨论:

我们已经知道原式为:

我们先来考虑几种情况:

以及的时候,此时原式将会转换为:。然后移项可得:,要让这个柿子的结果尽量大,我们就要让大,尽量小,这个很好理解:更大的减去更小的才能更大。

以及的时候,此时原式转换为:此时我们像情况一样,让尽量小,尽量大。

最后只要比较这两种情况谁大谁小就可以了:,这样我们就将复杂度缩小到

代码实现

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
struct xjh {
    int x,y;
} num[maxn];
int n,a,b=1e12,c,d=1e12;
inline int read() {
    int sum=0,ff=1; char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') ff=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        sum=sum*10+ch-48;
        ch=getchar();
    }
    return sum*ff;
}
int main() {
    n=read();
    for ( int i=1;i<=n;i++ ) {
        num[i].x=read(),num[i].y=read();
        a=max(a,num[i].x+num[i].y);
        b=min(b,num[i].x+num[i].y);
        c=max(c,num[i].x-num[i].y);
        d=min(d,num[i].x-num[i].y);
    }
    printf("%d\n",max(a-b,c-d));
    return 0;
}
全部评论

相关推荐

Twilight_mu:经典我朋友XXXX起手,这是那种经典的不知道目前行情搁那儿胡编乱造瞎指导的中年人,不用理这种**
点赞 评论 收藏
分享
虽然大家都在劝退读研,说读研以后也是打工,不如本科直接去打工,但随着现在研究生越来越多,很多企业招聘要求就会变成研究生起招,本科投递简历就会被卡,横向比较时也会因为"本科学历比不上研究生学历"被筛掉,而且你没发现劝退读研的基本都是读完研的人吗?而且进体制、国企等,研究生也比本科生升的快,他们拿着研究生文凭劝你一个本科生,可别当真了
炬火初现:肯定是说本科能有好工作或者满意的可以不读研啊,现在本科能找到好工作的那个不优秀,大学四年赛高中,而且还要和学校斗智斗勇,这种时候自然有的选,要是只是觉得一辈子混口饭吃,大概率也考不上研,或者考上又浑浑噩噩三年,也难说。 而且考研所谓的优势说实话是你用差不多四年的时间成本(考一年,读三年)换过来的,而且还未必读完有今年的就业市场,当然不能随便决定读。 再还要看专业,一些稀奇古怪的专业说实话根本没有办法创造出什么价值,也没钱赚(如果有爱好,可以适当降低报酬标准)。现在非92的研究生说实话也没啥太多所谓优势,难说。 所以任何时候都要具体情况具体分析,不能一概而论。 一点点小看法。欢迎大家友善讨论。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务