CF1562A The Miracle and the Sleeper 题解

笑死，晚上熬夜打CF比赛只过了A题还加了CF值！？

由于本人太弱，这道橙题都干了1h

题目描述

有 \(T\) 组数据，
给出一个区间\([l,r]\),在这个区间中选择2个数a,b，使它们a % b的值最大.

注意： \(l \le r \le 10^9\), \(T \le 10^3\)

解题步骤

暴力

CZC : 暴力优化一下就是正解了

这道题暴力时间复杂度是 \(O(n^2)\) 一定是会超时的，但我们也要先敲暴力，把该拿的分都拿了（~~虽然CF不计分只记做题数量~~），我们可以得到下面这一段代码

inline void test(int a,int b) {
    int ans=-100;
    for(int i=a;i<=b;i++) for(int j=a;j<i;j++) {
        cout<<"i="<<i<<" j="<<j<<" i%j="<<i%j<<endl;
        ans=max(ans,i%j);
    }
    printf("%d\n",ans);
}

然后直接样例爆炸

由于有输出调试，我们可以很快的发现规律 : 仿佛都是线性上升的，每次增加2

在一些情况下直接

cout << ((b - 1) << 1);

答案也是正确的。比如会超时的那个样例

在进行深入的研究就会发现答案的 \(a\) 都是这个区间的最大值。

对于暴力的代码我们只用看 \(a\) 就可以了

inline void test(int a,int b) {
    int ans=-100;
    for(int i=b,j=a;j<i;j++) {
        cout<<"i="<<i<<" j="<<j<<" i%j="<<i%j<<endl;
        ans=max(ans,i%j);
    }
    printf("%d\n",ans);
}

积累一下经验就可以思考一下正解了

正解

其实我也是思考了很久才想到正解，丢人

我们可以分析一下极端样例

1 1000000000

怎样 \(%\) 才能让结果最大呢？

分类讨论

我们可以把 \(1 ~ 1000000000\) 分成2段。

1 500000000
50000001 1000000000

好像这两段的答案都有共同之处。

我们可以发现最大的值其实是

499999999

其实就是 1000000000 % 500000001

同时用含有 b 的式子表示就是

\[(b - 1) / 2 \]

但有一些样例不符合这个规律比如：

99999999 1000000000

那这个答案又是什么呢？

慢慢的探索我们发现越接近 \(r / 2\) 模数越大，所以最后的答案是中间的部分，这种情况也可以这样想, 既然答案在中间，这里的区间已经不包含中间了，那答案是不是就应该为
b % a

Code

// QOJ没有这道题， 别找了！
#include<bits/stdc++.h>
using namespace std;
int T,a,b;
inline void test(int a,int b) {
    int ans=-100;
    for(int i=b,j=a;j<i;j++) {
        cout<<"i="<<i<<" j="<<j<<" i%j="<<i%j<<endl;
        ans=max(ans,i%j);
    }
    printf("%d\n",ans);
}
inline void solve(){
    scanf("%d%d",&a,&b);
    //test(a,b);
    if(a<=b/2)return (void)printf("%d\n",b-1>>1);
    return (void)(printf("%d\n",b%a));
}
int main(){
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}