题解 | 好好好数组

CSDN看到的一个另外一种容易想到的解法，原文链接

如果a[n]确定了，那么整个数组也就确定的，很容易发现，符合条件的数组一定是单调不降的，因为取模只会把数字变小，或者不变，不可能变大。

故当a[n]越小时，其往前的数字的可取值范围就越小，就更容易取到相同值，使数组出现不同种类的数字就更难，因此答案具有单调性，当a[n]越大，不同的种类也就不可能比之前还少。

check函数：每次枚举a[n]的大小，然后往前推，这样的时间复杂度是O(nlogn)的，但是注意到一个优化：当下标为i，值为a[i]时，若有a[i]<i，例如i=300,a[i]=1，那么由于一个数取模于比他大的数一定会不变，那么i=300,i=299,...,i=1都是a[i]，事实上可以直接略过，然后正解可以证明，check函数的循环不会运行超过4次

时间复杂度：O( T* logn)

#include <iostream>
#include <set>
using namespace std;

set<int> tmp;
bool check(int p,int n,int m){
	tmp.clear();
	tmp.insert(p);
	for(int i=n-1;p && i>=1;){
		if(p<i){
			i=p;//如果值小于了下标，则直接跳到对应下标
			continue;
		}
		p=p%i; //当前的等于上一次%i
		tmp.insert(p);
		i--;
	}
	return tmp.size()>=m;
}

int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int T;
	cin>>T;
	while(T--){
		int n,m;
		cin>>n>>m;
		int l=0,r=n; //二分在至少m个不同数字的情况下，a[n]至少需要尝试为几
		while(l<r){
			int mid=(l+r)>>1;
			if(check(mid,n,m))r=mid;
			else l=mid+1;
		}
		if(check(l,n,m))cout<<n-l+1;
		else cout<<0;
		cout<<"\n";
	}
}