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
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?