题意：分别在不同的起点出发，把糖果运到相应的编号的车站需要的最小距离，在每一站火车只能装一个糖果，相邻车站距离是 1.（i->i+1）
思路：因为只能装一个糖果，所以对于一个车站来说，有几个糖果就需要转好几圈，不同的是最后一圈可能会少些，因为不需要再回来了，这样花费 cost = （ 糖果个数 - 1 ） × 车站个数，对于最后一个来特别加一下就好了，当然就是最小的情况加上，因为最后一次尽量跑的小一些。
#include <bits/stdc++.h> using namespace std; const int maxn = 5005; int n, m; int a, b; vector<int> dis[maxn]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> a >> b; int x; if (b >= a) { x = b - a; } else { x = n - a + b; } dis[a].push_back(x); //起点到终点的距离 } for (int i = 1; i <= n; i++) { sort (dis[i].begin(), dis[i].end()); //每个起点按距离排序 } for (int i = 1; i <= n; i++) { //枚举火车起点 int res = -1; for (int j = 1; j <= n; j++) { //枚举站点 if (dis[j].size() == 0) { //如果该点没有要运送的糖果，跳过 continue; } int x = 0; if (j >= i) { //如果站点比起点大 x = j - i; } else { //如果站点比起点小 x = n - i + j; } int y = dis[j].size() - 1; //圈数减少1 x += y * n; //循环距离 x += dis[j][0]; //加上不够一圈的距离的最小值 res = max(res, x); } cout << res << " "; } return 0; }
