2017CCPC秦皇岛 A题Balloon Robot&&ZOJ3981【模拟】

题意：

一个机器人在长为M的圆形轨道上送气球，当机器人到达M号点的时候下一站会回到1号点，且全程不会停止运动。现在在长为M的轨道上有N个队伍，队伍会在某个时间做需要一个气球，机器人需要送过去。一共有P次请求，每一次请求a、b 表示a号在b时间需要气球。现在给定P次请求和N个队伍在轨道上的位置，机器人在0时刻可在轨道上的任意节点开始。计算从那个节点开始每个请求收到气球的时间t-请求的时间b的差的和的最小值。

思路：

任意选择一个起点，算出每次请求的t-b的值并保存在数组h中，值的范围在（0~m-1）之间。若起点向后移动一个则数组h中的数据都加一，且等于M的都变为0。由于M有10的9次方所以不能遍历所有的可能。
所以将h数组排序，每次将最大值变为0，即整个数组都加上（m-最大值）。

代码：

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

int main()

{

    int t;

    long long n,m,p;

    long long a[],h[];

    cin>>t;

    while(t--)

    {

        long long ans=;

        scanf("%lld%lld%lld",&n,&m,&p);

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

            scanf("%lld",&a[i]);

        for(int i=;i<p;i++)

        {

            long long x,y;

            scanf("%lld%lld",&x,&y);

            h[i]=(a[x]-(y%m)+m)%m;   //计算数组h,即某点开始的位次请求的值

            ans+=h[i];

        }

        long long sum=ans,pi=;

        sort(h,h+p);

        for(int i=p-;i>=;i--)

        {

            int g=;

            while(h[i-g]==h[i]&&i-g>=) g++; //求最大值的个数

            h[i]+=pi;   //pi表示再次之前已经补充了的最大值的数

            pi+=(m-h[i]);

            ans+=(p-g)*(m-h[i]);  // 计算此时的和

            ans-=g*h[i];

            sum=min(sum,ans);

            i-=g-;     //每次移动到下一个最大值

        }

        printf("%lld\n",sum);

    }

    return ;

}

巴特西

2017CCPC秦皇岛 A题Balloon Robot&&ZOJ3981【模拟】

最新文章

热门文章