UVALive6442_Coins on a Ring

真正的水题，可惜无法当场机智一下。

这样的，在一个圈圈上给你n个黑点，现在要你移动每一个黑点使得所有的点都是等间距的，每个点中最远需要一定的那个点最小可以是多少？

其实是这样来考虑的，我们可以随便设置一系列参考点，不妨直接假设为(0,n/m,2*n/m，……)，这样我们直接记录所有的点依次移动到这些对应位置所需要的最大的步奏和最小的步奏，这样我们就得到了到这一系列的位置的最大和最小值。这样我们需要的最终目标位置就是在最大值和最小值的中点处。

这里理解一下吧，就是答案了。。智商拙计。、、、

#include <iostream>

#include <cstdio>

#include <algorithm>

#define maxn 1000100

using namespace std;

int a[maxn],maxpos,minpos,n,m,cas=,t;

int main()

{

    scanf("%d",&t);

    while (t--)

    {

        scanf("%d%d",&n,&m);

        for (int i=; i<=m; i++) scanf("%d",&a[i]);

        sort(a+,a++m);

        maxpos=,minpos=~0U>>;

        for (int i=,cur=; i<=m; i++,cur+=n/m)

            maxpos=max(maxpos,a[i]-cur),minpos=min(minpos,a[i]-cur);

        printf("Case #%d: %d\n",++cas,(maxpos-minpos+)/);

    }

    return ;

}

巴特西

UVALive6442_Coins on a Ring

最新文章

热门文章