『FLA - III』Spectral

ScaredQiu · 2024-07-14 18:10:36 · 题解

模拟、数学

测试点 1 \sim 2

容易得到在 n=1 时答案为 k，在 n=2 时答案为 1.5k。

测试点 3 \sim 4

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

测试点 5

序列 T 的最大值是 T_2 和 T_3，读者可以自行查看题解结尾处的证明。

当 n=1 时答案为 k，否则答案为 1.5k。

单组数据时间复杂度 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;
}

证明：若 T_i > T_{i+1}，由于 T_{i+1}=k+ \dfrac{T_i}{i+1}，T_{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，因为 \dfrac{T_{i+1}}{i+2} 的分母更大，分子更小。

因为 T_{i+2}-T_{i+1}<0，所以 T_{i+1}>T_{i+2}，又因为 T_{i+1}>T_{i+2} 所以 T_{i+2}>T_{i+3}。以此类推，只要存在 T_i > T_{i+1}，那么对于所有大于 i 的整数 j 都有 T_i > T_j，又因为 T_3 > T_4，所以序列 T 的最大值只可能在 T_1,T_2,T_3 中取到，可知序列 T 的最大值为 T_2=T_3=1.5k。