2024ICPConline部分题目

L

题目链接：2024ICPConline L

设在[1,T]的范围内，d[ i ]为数为i时的期望，此时答案为d[T]。

可以猜想得存在k，使[1,k]内的数不操作直接减更优，而[k+1,T]内的数操作更优。

由于操作纯随机，故当i>k时，d[i]的值相等（因为一定会进行操作），设为x。

可由T必须操作得到方程：

$$k/T*(k+1)/T+(T-k)/T*(x+1)=x$$

方程解释：因为必须操作，故有$k/T$的概率为[1,k]内的数，有$(T-k)/T$的概率得到[k+1,T]内的数。

化简得：

$$k/2-1/2+T/k=x$$

由基本不等式得，当$k= \sqrt[2]{T}$时，x最小。

故当$k=\lceil \sqrt[2]{T} \rceil$或$k=\lfloor \sqrt[2]{T} \rfloor$时x取最小。

代码（队友写的）：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double

ll gcd(ll m, ll n) {
    return n ? gcd(n, m%n) : m;
}
ll cmp(ll a,ll b,ll c,ll d)
{
    if(a*d<b*c) return -1;
    if(a*d==b*c) return 0;
    if(a*d>b*c) return 1;
}
void huajian(ll &a,ll &b)
{
    ll g = gcd(a, b);
    a /= g;
    b /= g;
}
void solve(){
    ll t;
    cin >> t;
  
    ll k = sqrt(2*t);
    if(k*k!=2*t)
    {
        ll a = k*(k-1)+2*t , b = 2*k, c = (k+1)*k+2*t , d = 2*(k+1);  
        huajian(a,b);
        huajian(c,d);
        if(cmp(a,b,c,d)==-1)
        {
            cout<<a<<" "<<b<<"\n";
        }
        else
        {
            cout<<c<<" "<<d<<"\n";
        }
    }
    else
    {
        ll a = k*(k-1)+2*t;
        ll b = 2*k;
        huajian(a,b);
        cout<<a<<" "<<b<<"\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll T;
    cin >> T;
    while(T--) solve();
    return 0;
}