Problem - 1129A2 - A2. Toy Train(暴力+贪心)

A2. Toy Train

题目大意:一辆火车从$1$到$n$循环运动,有$m$个货物需要从$u$运输到$v$,求从$1$到$n$这些不同的站点出发,最少需要多久才能把所有的货物都送到.(火车在某个站一次只能装载一个货物,火车可以卸掉任意多的货物).

解题思路:如何将总时间缩短,首先总时间一定受到每个站台货物数量的限制,如果某个站台的货物量$nu{m}_i$是最大的,那么火车必须先跑完$nu{m}_i?1$次循环,然后继续跑完当前的货物,还有一种需要考虑的情况是$nu{m}_i=nu{m}_{max}?1$,这种情况,送完其所需要的花费也可能是最大,对于每个站台只需要枚举所有的站台的情况即可.然后是对于每个站台的货物,怎么送才能使得总时间最小,这个贪心策略就是先把到达目标距离远的先送了,因为前面规则的限制,火车一定是要跑完大循环的,先跑完了路程较远的货物,最后的货物送起来可以减小最后一轮的花费.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
struct node{
    int to, dis;bool operator<(node&a){
    return dis<a.dis;}
};
const int N = 5e3+5;
vector<node>a[N];
int main(){
    syncfalse#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endifint n, m, u, v;cin>>n>>m;for (int i = 1; i <= m; ++i){
    cin>>u>>v;a[u].push_back({
    v, (v-u+n)%n});}int maxd = 0;for (int i = 1; i <= n; ++i){
    sort(a[i].begin(), a[i].end());maxd=max(maxd, int(a[i].size()));}for (int i = 1; i <= n; ++i){
    int ans = 0;for (int j = 1; j <= n; ++j){
    if (a[j].size()==maxd){
    ans=max(ans, n*(maxd-1)+(j-i+n)%n+a[j][0].dis);}else if (a[j].size()==(maxd-1)&&maxd!=1){
    ans=max(ans, n*(maxd-2)+(j-i+n)%n+a[j][0].dis);}}cout << ans << " ";}return 0;
}