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;
}