題目要求

P1708題目鏈接

分析

這題挺有意思的，看起來是一個復雜的優化問題，其實很水。

主要是題給了很多限定條件，比如中轉站和天然氣井的個數相等，最后還是一一對應的，求得距離只是走橫向或縱向的……

做個比方吧，假設有3個天然氣井（a、b、c）和3個中轉站（d、e、f），由于一一對應，所以假設隨便對應。

$$\begin{gathered} distanc{e}_x=(x_a?xd)+(x_b?x_e)+(x_c?x_f) \\ distanc{e}_y=(y_a?yd)+(y_b?y_e)+(y_c?y_f) \\ distance=|distanc{e}_x|+|distanc{e}_y| \end{gathered}$$

由于加減法具有結合律，所以說隨便換，括號也可以拆。

也就是說，只需簡單的將天然氣井的x求和，再將中轉站的x求和，二者作差取絕對值，y同理，絕對值相加就是答案。

有一個小坑是，數據會出現爆int的情況，應該用long long。

AC代碼

#include <iostream>using namespace std;int main() {int n;cin >> n;long long x = 0, y = 0, temp;for (int i = 0; i < n; i++) {cin >> temp;x += temp;cin >> temp;y += temp;}for (int i = 0; i < n; i++) {cin >> temp;x -= temp;cin >> temp;y -= temp;}cout << abs(x) + abs(y) << endl;return 0; }

總結

以上是生活随笔為你收集整理的天然气井（洛谷P1708题题解，C++语言描述）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。