有一张有n个点的有向图，有(frac{n(n-1)}{2})条边，其中不存在双向边，请使用不超过10000次询问，寻找到图中的一条未规定起点和终点的halmiton的路径，即一条路径不重不漏地经过所有点，(nleq 1000)。
解
交互要最少询问次数的题目，显然是一道二分的题目，不存在双向边，即一个有向完全图，而二分需要对序列二分，所以不妨假设已经确定好了经过前k-1个点的路径，第1个点为终点，现在问题就变成了第k点放在路径中的哪一个位置，于是我们二分这个位置mid，含义是放在mid前，二分区间([l,r])，如果mid指向k，那么令(r=mid-1)，否则令(l=mid+1)
求证：以上操作必然找到一个位置满足条件
证明：
对于mid而言如果mid指向k那么令--mid，继续进行同样地判断一直到第一个点或者是存在一个点由k指向，那么这个位置就是合法的，显然必然存在这个位置。
对于mid而言k指向mid，令++mid，一直这样操作，知道找到一个位置该点指向mid，或者到了最后一个位置，就寻找到一个合法的位置，显然必然存在这个位置。
于是得证。
因此我们就可以在({large nlog_2^n})次询问中得到答案，但是这是一道交互题，注意一些细节，对于vector，如果没有元素end指针是指向begin指针的，于是当向后二分未搜到合法位置，而返回最后一个位置+1来插入的，注意没有元素时会段错误，其他情况下这种做法是可行的。
参考代码
#define il inline
class Solution {
public:
vector<int>czf;
vector<int> specialSort(int N) {
czf.push_back(1);
for(int i(2);i<=N;++i)
czf.insert(czf.begin()+dfs(0,czf.size()-1,i),i);
return czf;
}
il int dfs(int l,int r,int x){
int mid;
while(l<=r){
mid=l+r>>1;
if(compare(czf[mid],x))l=mid+1;
else r=mid-1;
}return l;
}
};
其实还有一个很好的想法，既然是一大小比较的问题，为什么一个一个数不插入平衡树呢，下面献上我的超时代码供各位嘲笑。
class Solution {
public:
#define il inline
struct point{
int id;
il bool operator<(const point&a)const{
return compare(id,a.id);
}
};
vector<int> specialSort(int N) {
set<point>S;
for(int i(1);i<=N;++i)S.insert((point){i});vector<int>czf;
for(set<point>::iterator i(S.begin());i!=S.end();++i)
czf.push_back(i->id);return czf;
}
};