本文主要是介绍Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2)D2. Toy Train(思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://codeforces.com/contest/1130/problem/D2
题目大意：有n个车站，按照环前进，有m条要求从x送到y，每次从x最多能拿一个糖，输出在第i个车站出发最少需要多少时间完成所有要求
题目思路：根据要求得到每个点需要送出的糖果数，并且把每个点要到的地方存一下。枚举第s个车站出发，然后枚举每一个点，计算到达这个点以及把这个点需要送的货送完的最少时间。首先需要从s车站到i点，然后有多少糖果就需要转糖果数-1圈，因为一次最多拿一个，所以每次都要回来拿。然后最后一次到达目的地即可。前面都是固定的，主要是最后一次到达目的地的距离。所以需要枚举目的地，看到哪个最短就用哪个。然后就得到了完成所有目标的时间，输出即可。
以下是代码：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
using namespace std;
const int MAXN = 1e5+5;
int n,m;
struct node{int x,y;
}a[MAXN];
int out[MAXN];
vector<int>v[MAXN];
int dist(int x,int y){if(y>=x)return y-x;else return n-x+y;
}
int main()
{while(~scanf("%d%d",&n,&m)){rep(i,1,n)v[i].clear();rep(i,1,m){scanf("%d%d",&a[i].x,&a[i].y);out[a[i].x]++;v[a[i].x].push_back(a[i].y);}rep(s,1,n){int ans=0;rep(i,1,n){int ans1=dist(s,i)+(out[i]-1)*n;int temp=inf,len=v[i].size();if(!len)continue;rep(j,0,len-1){temp=min(temp,dist(i,v[i][j]));}ans1+=temp;ans=max(ans1,ans);}cout<<ans<<" ";}cout<<endl;}return 0;
}
这篇关于Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2)D2. Toy Train(思维)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
