有一个环形的公路，上面共有站，现在给定了顺时针第站到第站之间的距离（特殊的，也给出了第站到第 1 站的距离）。小美想沿着公路第站走到第站，她想知道最短的距离是多少？
区块链毕设网qklbishe.com为您提供问题的解答
有一个环形的公路，上面共有站，现在给定了顺时针第
站到第
站之间的距离（特殊的，也给出了第
站到第 1 站的距离）。小美想沿着公路第
站走到第
站，她想知道最短的距离是多少？
#include "bits/stdc++.h" using namespace std; /** * 解题思路：前缀 * 从A到B和从B到A，路径是一样的或周长-路径 * 最多不会跨越一个圆的距离 * */ int main() { int n; cin >> n; vector<ULL> prefix(n+1, 0); for (int i = 1; i <= n; i++) { cin >> prefix[i]; prefix[i] += prefix[i-1]; } int x, y; cin >> x >> y; if (x == y) { cout << 0 << endl; return 0; } if (x > y) swap(x, y); const ULL res = prefix[y-1] - prefix[x-1]; const ULL rev_res = prefix[n] + prefix[x-1] - prefix[y-1]; cout << (res < rev_res ? res : rev_res) << endl; return 0; }
编辑于 2024-08-23 15:07:13
以上就是关于问题有一个环形的公路，上面共有站，现在给定了顺时针第站到第站之间的距离（特殊的，也给出了第站到第 1 站的距离）。小美想沿着公路第站走到第站，她想知道最短的距离是多少？的答案
欢迎关注区块链毕设网-
web3一级市场套利打新赚钱空投教程
区块链NFT链游项目方科学家脚本开发培训
.jpg){kind=link}