【Codeforces 1129A】Toy Train

【链接】我是链接,点我呀:)

【题意】

火车从1,2,3...n->1的方式绕圈走。(即每次从i走到i+1)
有一些点有货物需要装载,但是每个点只能装上去一个货物。
每个货物都有目标点卸货点(卸货的时候不限量)
问你假设火车起点为s(s=1,2,3...n)时,完成所有点的装货卸货任务需要的最小时间。

【题解】

会发现其实每个点出去的任务都是互相独立的。
某个点在做运载任务的时候,其他人也可以同时进行运载任务(路过了就捎上它的运载物就行,反正装运不需要时间)。
那么现在的问题仅仅是,让每个点完成所有任务的时间最短。
然后取所有点完成任务的时间中最长的那个作为答案就好了。
设第i个点的任务个数为cnt[i]
每个点i完成所有任务的时间为
起点s到i所需的时间+n*(cnt[i]-1)+cnt[i]个任务中所需时间最短的那个任务所用时间
前cnt[i]-1个任务肯定要绕cnt[i]-1圈然后回到原来的位置的.
最后一个任务才是关键,我们只要让最后一个任务的时间最短,那么肯定第i个点的所有任务完成的时间也就最短了。

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 5000;

int n,m;

int mi[N+10],cnt[N+10];

int get_dis(int x,int y){

    if (y>=x) return y-x;

    else return y+n-x;

}

int main(){

    ios::sync_with_stdio(0),cin.tie(0);

    cin >>n >> m;

    for (int i = 1;i <= m;i++){

        int x,y;

        cin >> x >> y;

        cnt[x]++;

        if (mi[x]==0)

            mi[x]=get_dis(x,y);

        else

            mi[x] = min(mi[x],get_dis(x,y));

    }

    for (int i = 1;i <= n;i++){

        int ans = 0;

        for (int j = 1;j<=n;j++){

            ans = max(ans,get_dis(i,j)+n*(cnt[j]-1)+mi[j]);

        }

        cout<<ans<<" ";

    }

	return 0;

}

巴特西

【Codeforces 1129A】Toy Train

最新文章

热门文章