您当前的位置: 首页 >  c++

星拱北辰

暂无认证

  • 0浏览

    0关注

    1205博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

天然气井(洛谷P1708题题解,C++语言描述)

星拱北辰 发布时间:2021-02-17 20:31:28 ,浏览量:0

题目要求

P1708题目链接

在这里插入图片描述

分析

这题挺有意思的,看起来是一个复杂的优化问题,其实很水。

主要是题给了很多限定条件,比如中转站和天然气井的个数相等,最后还是一一对应的,求得距离只是走横向或纵向的……

做个比方吧,假设有3个天然气井(a、b、c)和3个中转站(d、e、f),由于一一对应,所以假设随便对应。

d i s t a n c e x = ( x a − x d ) + ( x b − x e ) + ( x c − x f ) d i s t a n c e y = ( y a − y d ) + ( y b − y e ) + ( y c − y f ) d i s t a n c e = ∣ d i s t a n c e x ∣ + ∣ d i s t a n c e y ∣ distance_{x}=(x_{a}-x{d})+(x_{b}-x_{e})+(x_{c}-x_{f})\\distance_{y}=(y_{a}-y{d})+(y_{b}-y_{e})+(y_{c}-y_{f})\\distance=|distance_{x}|+|distance_{y}| distancex​=(xa​−xd)+(xb​−xe​)+(xc​−xf​)distancey​=(ya​−yd)+(yb​−ye​)+(yc​−yf​)distance=∣distancex​∣+∣distancey​∣

由于加减法具有结合律,所以说随便换,括号也可以拆。

也就是说,只需简单的将天然气井的x求和,再将中转站的x求和,二者作差取绝对值,y同理,绝对值相加就是答案。

有一个小坑是,数据会出现爆int的情况,应该用long long。

AC代码
#include 

using namespace std;

int main() {
    int n;
    cin >> n;
    long long x = 0, y = 0, temp;
    for (int i = 0; i > temp;
        x += temp;
        cin >> temp;
        y += temp;
    }
    for (int i = 0; i > temp;
        x -= temp;
        cin >> temp;
        y -= temp;
    }
    cout             
关注
打赏
1660750074
查看更多评论
0.0524s