L、502 Bad Gateway
题意：
给定一个 T T T，每一步可以做以下两个操作：
1、减1
2、随机重置为 [ 1 , T ] [1,T] [1,T]中的某个整数
求在最优策略下，得到 0 0 0的期望步数
思路：
最优策略为选择一个阈值 S S S，如果大于 S S S的话，就重置；如果小于 S S S的话就直接减到 0 0 0
所以我们可以列出下面这个方程
E = S × ( 1 + S ) 2 × ( S + 1 ) × ( T − S ) T E=\frac{\frac{S\times(1+S)}{2}\times(S+1)\times(T-S)}{T} E=T2S×(1+S)×(S+1)×(T−S)
可以解得
E = S − 1 2 + T S = S 2 + T S − 1 2 E=\frac{S-1}{2}+\frac{T}{S}=\frac{S}{2}+\frac{T}{S}-\frac{1}{2} E=2S−1+ST=2S+ST−21
所以能得到期望的最大值在 S = 2 T S=\sqrt{2T} S=2T取得
所以在 ⌊ 2 T ⌋ \lfloor \sqrt{2T} \rfloor ⌊2T⌋和 ⌈ 2 T ⌉ \lceil \sqrt{2T}\rceil ⌈2T⌉两点取
void solve(){int t;cin >> t;int x1 = (int)sqrt(2*t);int x2 = min(t,x1+1);int fz1 = x1*x1 + 2*t - x1;int fm1 = 2*x1;int g1 = __gcd(fz1,fm1); fz1 /= g1;fm1 /= g1;int fz2 = x2*x2 + 2*t - x2;int fm2 = 2*x2; int g2 = __gcd(fz2,fm2);fz2 /= g2;fm2 /= g2;if(fz1*fm2<=fz2*fm1) cout << fz1 << " " << fm1 << endl;else cout << fz2 << " " << fm2 << endl;}
