1

小刘家里有n个鸟蛋，大小为a_i，并且大小互不相同，他有n个孵蛋器，第i个孵蛋器每天可以长大i。那么最早几天会有同样大小的蛋出现，规则：最大的鸟蛋放最慢的，最小的放最快的，其它依类次类推。

要求：1s，内存大小忘了。

输入：1<=n<=10^6

1<=a_i<=10^9

例子：

输入：3

8 4 2

输出：2。

这个其实很好算。（8-4）/（2-1）=4

（4-2）/（3-2）=2

（8-2）/（3-1）=3

所以是2。

#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include <cmath>
using namespace std;
int main()
{int n,m;cin>>n;vector <int> a(n),s;for(int i=0;i<n;i++){cin>>a[i];}for(int i=n;i>0;i--){for(int j=1;j<i;j++){s.push_back( ceil((a[j-1]-a[i-1])/((double)i-j)) );}}cout<<*min_element(s.begin(),s.end());
}

这个是我一开始的代码，我记得测试的通过率是50%，但是内存太大了，而且有瑕疵。空间复杂度为O(n^2)。

int的范围已经包括了10^9。

改进的话，主要是改进空间。

#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include <cmath>
using namespace std;
bool cmp(int a,int b)
{return a>b;
}int main()
{int n=4,m;const int MAX=10000;// cin>>n;int a[n]={21,16,9,1},s[n-1];sort(a,a+n,cmp);// for(int i=0;i<n;i++)// {//     cin>>a[i];// }for(int i=n-1;i>0;i--)//n-1---1{for(int j=0;j<i;j++)//0到i-1{if((a[j]-a[i]) % (i-j)){s[j]=MAX;}else{s[j]=(a[j]-a[i])/(i-j);}}s[i-1]=*min_element(s,s+i);}cout<< *min_element(s,s+n-1);return 0;
}

这样s数组是复用的，大大节省了空间。min_element返回最小值的指针，它其实用选择排序一轮就可以得到，复杂度为O(n)。

整体复杂度O(n^2)，空间复杂度为O(n)。

从a[n-1]和a[0]-a[n-2]比较，存最小值，如果不能整除给个很大的值。

然后a[n-2]和a[0]到a[n-3]逐个操作，也存起来。

最后找最小值的最小值。

可以在1s内结束。

我其实还有一种其他的思路，就是先比较2个的，然后比较三个的，以此类推，复杂度也是O(n^2)，空间复杂度也是O(n)。

#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include <cmath>
using namespace std;
bool cmp(int a,int b)
{return a>b;
}
int main()
{int n=3,m;const int MAX=10000;// cin>>n;int a[n]={8,4,2},s[n];sort(a,a+n,cmp);s[n-1]=a[0]-a[1];for (int i = 2; i < n; ++i){for (int j = 0; j <i; ++j){if ((a[j]-a[i])%(i-j)){s[j]=MAX;}else{s[j]=(a[j]-a[i])/(i-j);}}s[n-1]=min(s[n-1],*min_element(s,s+i));}// for(int i=0;i<n;i++)// {//     cin>>a[i];// }cout<< s[n-1];return 0;
}