Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2) |
|---|
Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 1)
题意：分别在不同的起点出发，把糖果运到相应的编号的车站需要的最小距离，在每一站火车只能装一个糖果，相邻车站距离是 1.
&：因为只能装一个糖果，所以对于一个车站来说，有几个糖果就需要转好几圈，不同的是最后一圈可能会少些，因为不需要再回来了，这样花费 cost = （ 糖果个数 - 1 ） × 车站个数，对于最后一个来特别加一下就好了，当然就是最小的情况加上，因为最后一次尽量跑的小一些。
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
typedef long long ll;
const int maxn = 250;
vector<int>st[maxn];
int n,m;
int a,b;
int main()
{
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i )
{
scanf("%d %d", &a, &b);
int x;
if(b >= a) x = b - a; // 从该车站到目的地的花费
else x = n - a b; // 如果是 5 2 ，那么是后半圈
st[a].push_back(x);
}
for(int i = 1; i <= n; i )
{
sort(st[i].begin(), st[i].end()); // 排序
}
for(int i = 1; i <= n; i ) // 每个站点作为起点
{
int res = -1;
for(int j = 1; j <= n; j )
{
if(!st[j].size()) continue; // 如果没有糖果了，就不用停下来装了
int x = 0;
if(i <= j) x = j - i; // 从起始点到有糖果的点的距离
else x = n - i j;
int y = st[j].size() - 1; // 糖果数量 - 1 都需要重新回来装
x = y * n; // 这些糖果都要回到这个点装，所以每次都是 n 个距离
x = st[j][0]; // 最后一个装需要走的距离最小的糖果就可以了
if(res < x) res = x;
}
printf("%d ",res);
}
return 0;
}版权声明：本文为CSDN博主「Mercury_Lc」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Mercury_Lc/article/details/88063269
