[信息与未来 2015] 拴奶牛

题目描述

有 $n$ 头奶牛，有 $k$ 个木桩，每个木桩有一个位置，一个木桩上只能拴一头奶牛。由于奶牛好斗，所以在拴奶牛的时候，要求距离最近的奶牛的距离尽可能大。

例如 $n=4,k=6$，木桩的位置为 $0,3,4,7,8,9$，此时为下图。

有许多种拴牛方案，例如：

• $0,3,4,9$：此时最近距离为 $1$（$3,4$ 之间）；
• $0,3,7,9$：此时最近距离为 $2$。

输入格式

三个整数 $n,k,p_1$，其中 $p_1$ 为第 $1$ 个木桩的位置，其他木桩 $p_i(i\ge2)$ 的位置由下面公式给出：

$p_i = p_{i-1} + ((p_{i-1}\times2357+137) \bmod 10)+1$。

输出格式

一个整数，即奶牛间最近距离的最大值。

样例 #1

样例输入 #1

25 70 99

样例输出 #1

12

提示

$1\le n\le k\le10^6,0\le p_1\le100$。

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int n,k,p1;
bool check(int x)
{
    int cnt=1;
    int p=a[0];
    for(int i=1;i<=k-1;i++)
    {
        if(a[i]-p>=x)
        {
            cnt++;
            p=a[i];
        }
    }
    if(cnt<=n)
    {
        return true;
    }else
        return false;
}
int main()
{
    
    cin>>n>>k>>p1;
    a[0]=p1;
    for(int i=1;i<=k-1;i++)
    {
        int s=a[i-1]+((a[i-1]*2357+137)%10)+1;
        a[i]=s;
    }
    for(int i=0;i<=k-1;i++)
    {
		cout<<a[i]<<" ";
	}
    int l=1,r=a[k-1]-a[0];
    while(l<r)
    {
    	int mid=(l+r)/2;
        if(check(mid))
        {
            r=mid;
        }else
            l=mid+1;
    }
    cout<<r;
}