随机算法 && CodeForces

传送门

解题思路

先读懂题目：

有一个等差数列（未排序），共有n个数字，需要你猜出公差和最小的数字。

你共有60次询问机会，每一次有两种选择：

？i，返回ai的值
> i，返回是否存在一个数严格大于i

最后给出答案。

思路?

首先用二分查找得到最大值，使用最多三十次左右询问次数（a<=10^9）。

然后在用随机数求得公差，即可得到首项。

那么随机数如何求得公差呢？

把剩下的次数全部耗尽，寻味数字，排序，求查分数组，把查分数组中的所有差取gcd，则极大概率为正确答案。

证明？略。

所以随机算法就是用随机数多次询问某一值，然后高概率求出正确答案。

AC代码

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<queue>
 8 #include<set>
 9 #include<map>
10 #include<vector>
11 #include<iomanip>
12 #include<ctime>
13 #include<stack>
14 using namespace std;
15 const int maxn=1000000000;
16 int n,maxa,l,r=maxn,cnt,num,ans,a[1000005];
17 bool check(int a){
18     cnt++;
19     int x;
20     printf("> %d
",a);
21     fflush(stdout);
22     scanf("%d",&x);
23     return x;
24 }
25 int gcd(int a,int b){
26     if(b==0) return a;
27     return gcd(b,a%b);
28 }
29 int main()
30 {
31     srand(time(NULL)+20200131);
32     cin>>n;
33     while(l<r){
34         maxa=(l+r)/2;
35         if(check(maxa)) l=maxa+1;
36         else r=maxa;
37     }
38     maxa=l;
39     for(int i=cnt+1;i<=60;i++){
40         printf("? %d
",rand()*rand()%n+1);
41         fflush(stdout);
42         scanf("%d",&a[++num]);
43     }
44     sort(a+1,a+num+1);
45     ans=a[2]-a[1];
46     for(int i=3;i<=num;i++){
47         ans=gcd(ans,a[i]-a[i-1]);
48     }
49     cout<<"! "<<maxa-(n-1)*ans<<" "<<ans;
50     return 0;
51 }