Codeoforces 201E. Thoroughly Bureaucratic Organization-贪心+二分+脑洞题

题意：

有一个长度为n的排列A，你想通过一些询问知道它是什么样的. 每次你构造一个长度为k(0<k≤m)的序列B,满足 $1≤B_i≤n$ 且B中没有相同的元素，系统会根据序列B生成一个长度为k的序列C，Ci的值为 $A_{B_i}$ ,然后打乱C序列后返回给你,问至少要多少次询问才能知道A究竟是什么

$n,m≤10^9$ 数据组数 $10^3$

Solution：

神题。

考虑二分，二分一个答案x，求询问x次所能得到的最大的序列长度maxn，然后比较maxn和n的关系进行二分

那么问题在于知道了询问的次数x和每次最多询问的个数m，如何求maxn呢？

我们把每次询问的数设成1，没有被询问道的数设成0，这样我们就得到了一个x*maxn的表格

1.考虑如何才能确定出这maxn个数：每一竖行的01字符串两两不相等即可，因为如果出现了两个数在x个询问中的出现情况一样，就分不清这两个数了

2.考虑这道题本身的限制条件：每一横行的01字符串中最多出现m个1

然后我们就需要一个结论：存在一个合法方案是表格中1的个数不超过k*m的充分必要条件，充分性很显然，必要性也可以证明：第一个条件很好满足，那么我们考虑一个满足1条件，不满足2条件的方案：

假设第x行出现1的次数超过了m，第y行出现1的次数小于m，

我们于竖行找出第x行是1，在第y行是0的字符串，假设一共有X个，再找出第x行是0，在第y行是1的字符串，假设一共有Y个，可以得到X>Y，然后我们考虑把所有X个字符串第x行赋值为0，在第y行赋值为1，那么最多出现重复Y个，多余的有些就被转化成了合法的情况，我们每次转化一定会减少不合法的数量，重复多次后就得到了合法的方案了

知道这个重要的结论后，我们就可以贪心了：贪心地选择1出现次数尽量少的字符串，我们可以从小到大枚举1出现的个数，在满足的限制的情况下不停地加就好了

注意可能会爆longlong

代码：

#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
using namespace std;
int t;
int n,m;
int check(int x)
{
	long long tot=1ll*x*m;
	long long C=1;
	long long num=1;
	int k=0;
	while (tot&&k<=x)
	{
		k++;
		C=C*(x-k+1)/k;
		if (tot-C*k>=0) num+=C,tot-=C*k;
		else num+=tot/k,tot=0;
		if (num>n) return 0;
		
	}
	if (num>n) return 0;
	else if (num<n) return 1;
	else if (num==n) return 2;
}
int main()
{
	scanf("%d",&t);
	while (t--)
	{
		scanf("%d%d",&n,&m);
		int l=0,r=n,ans=n;
		while (l<=r)
		{
			int mid=l+r>>1;
			int nw=check(mid);
			if (nw==0) ans=mid,r=mid-1;
			else if (nw==1) l=mid+1;
			else {ans=mid;break;}
		}
		printf("%d\n",ans);
	}
}