11 条题解

  • -2
    @ 2024-7-14 20:23:17

    模拟、数学


    测试点 121 \sim 2

    容易得到在 n=1n=1 时答案为 kk,在 n=2n=2 时答案为 1.5k1.5k

    测试点 343 \sim 4

    暴力计算 T1TnT_1 \sim T_n 后取最大值。

    测试点 55

    ii 00 11 22 33 44 55 \cdots
    TiT_i 00 kk 1.5k1.5k 1.375k1.375k 1.275k1.275k \cdots

    序列 TT 的最大值是 T2T_2T3T_3,读者可以自行查看题解结尾处的证明。

    n=1n=1 时答案为 kk,否则答案为 1.5k1.5k

    单组数据时间复杂度 O(1)O(1)

    #include<bits/stdc++.h>
    using namespace std;
    int T,n,k;
    int main(){
        scanf("%d",&T);
        while(T--){
            scanf("%d%d",&n,&k);
            if(n==1) printf("%d.0\n",k);
            else if(k%2==0) printf("%d.0\n",k+k/2);
            else printf("%d.5\n",k+k/2);
        }
        return 0;
    }
    

    证明:若 Ti>Ti+1T_i > T_{i+1},由于 Ti+1=k+Tii+1T_{i+1}=k+ \dfrac{T_i}{i+1}Ti+2=k+Ti+1i+2T_{i+2}=k+ \dfrac{T_{i+1}}{i+2},那么 $T_{i+2}-T_{i+1}=\dfrac{T_{i+1}}{i+2}- \dfrac{T_i}{i+1}<0$,因为 Ti+1i+2\dfrac{T_{i+1}}{i+2} 的分母更大,分子更小。

    因为 Ti+2Ti+1<0T_{i+2}-T_{i+1}<0,所以 Ti+1>Ti+2T_{i+1}>T_{i+2},又因为 Ti+1>Ti+2T_{i+1}>T_{i+2} 所以 Ti+2>Ti+3T_{i+2}>T_{i+3}。以此类推,只要存在 Ti>Ti+1T_i > T_{i+1},那么对于所有大于 ii 的整数 jj 都有 Ti>TjT_i > T_j,又因为 T3>T4T_3 > T_4,所以序列 TT 的最大值只可能在 T1,T2,T3T_1,T_2,T_3 中取到,可知序列 TT 的最大值为 T2=T3=1.5kT_2=T_3=1.5k

信息

ID
13
时间
1000ms
内存
512MiB
难度
2
标签
递交数
1259
已通过
336
上传者