题目链接：
UVALive 6442 Coins on a Ring
题意：
一个圆环上有n个位置，编号为0–n-1,已知存在m个点，需要移动这些点使得这些点两两间隔距离为n/m，输入保证m是n的因数，问最移动每个点的最大步数的最小值是多少？即在所有可行方案中，第i个方案有一个单点移动最大值move_max[i]，需要知道min(move_max[i])。
分析：
因为数据范围是n<=1e6,并且如果通过单点最大k步移动可以是这些点两两间隔n/m，那么对于任意的k’(k’>k)也一定是可以的。所以可以二分查找需要的最小单点最大移动步数。当单点移动最大步数确定为d时如何判断d是否能使得这些点均匀分布呢？
考虑每个点的移动区间，假设第i-1个点的移动区间是[prelow,prehigh]，因为第i点最多可移动d步，所以第i个点的移动区间是[data[i]-d,data[i]+d],又因为第i-1个点和第i个点需要间隔step=n/m，所以第i-1个点给第i个点的约束移动区间是[prelow+d,prehigh+d],所以第i个点的实际允许移动区间是
curlow=max(prelow+d,data[i]-d), curhigh=min(prehigh+d,data[i]+d);
只要对每个点判断这个区间是否存在即curlow<=curhigh是否成立，就能判断d是否合法了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
using namespace std;
const int MAX_N=1000010;int T,n,m,step,cases=0;
int data[MAX_N];inline bool check(int d)
{int prelow,prehigh,curlow,curhigh;prelow=data[0]-d;prehigh=data[0]+d;for(int i=1;i<m;i++){curlow=max(prelow+step,data[i]-d);curhigh=min(prehigh+step,data[i]+d);if(curlow>curhigh) return false;prelow=curlow;prehigh=curhigh;}return true;
}int main()
{//freopen("Fin.txt","r",stdin);scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=0;i<m;i++){scanf("%d",&data[i]);}sort(data,data+m);step=n/m;int left=0,right=n;while(right>left){int mid=(left+right)/2;if(check(mid)){right=mid;}else {left=mid+1;}}printf("Case #%d: %d\n",++cases,left); //left==right}return 0;
}