题解 P1708 【天然气井】

· · 题解

题目传送门

思路：

首先看一眼数据范围，接着看一眼试题难度，便得出了一个看似非常粗暴，实际为正解的算法

方法：

直接把所有的天然气井的横纵坐标分别相加，然后再分别减去所有的中转站的横纵坐标即可（证明过程见尾部）

注意事项：

1.最后输出答案的时候记得取绝对值，否则会红色一片。
2.由于数据很大，一定要记得开long long，否则会WA 16 21 23 25 号点。
3.测试数据没有问题，不需要学习楼下的同志打表。

代码：

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long i,j,k,m,n,sumx=0,sumy=0;
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        scanf("%lld%lld",&k,&m);
        sumx+=k;
        sumy+=m;
    }
    for(i=1;i<=n;i++){
        scanf("%lld%lld",&k,&m);
        sumx-=k;
        sumy-=m;
    }
    printf("%lld",abs(sumx)+abs(sumy));
    return 0;
}

证明过程：

相信大家可以很简单的想明白，由于天然气井的数量等于中转站的数量，所以对于每一座天然气站都会有一座唯一确定的中转站，而他们之间的距离就等于横纵坐标差的和，由此可证明。