题解：P13009 【MX-X13-T4】「KDOI-12」好胜是人的本能，功利是社会的本性。

· · 题解

P13009

特殊性质启发我们应该考虑分类做。

  1. 当 a_i\le \sqrt m 时：

    此时 \dfrac{m}{a_i}\ge\lfloor \dfrac{m}{a_i}\rfloor \ge a_i，则 \dfrac{m}{\lfloor \dfrac{m}{a_i}\rfloor}\ge a_i。因此 a_i 的值会越来越接近 \sqrt m，a_i 会越来越小。而 a_i 只变换一次便是最大的情况（a_i=\lfloor \dfrac{m}{a_i}\rfloor 例外，需特判）。

  2. 当 a_i>\sqrt m 时：

    此时 a_i\ge \dfrac{m}{a_i}\ge\lfloor \dfrac{m}{a_i}\rfloor，则 \dfrac{m}{\lfloor \dfrac{m}{a_i}\rfloor}\ge a_i。因此 a_i 经过变换后会越来越大，直到一个定值，记做了 v_i 次后进入循环。直接暴力枚举算出变换次数即可，复杂度类似于数论分块（？。发现一个性质，在这之后变换 2x 次 a_i 都是最大值（对后面有用）。

处理完以上内容后，发现情况 1 的相邻数字可以合在一起，操作次数为 1；情况 2 的相邻数字可以合在一起，操作次数为 V=\max_{i=l}^{r}{v_i}（因为比最大值小的数可以用上面的性质补平成最大值）；对于 a_i=\lfloor \dfrac{m}{a_i}\rfloor 的情况，无论分在哪边都可以，可以直接无视。

这样，每个块就被压缩成单点操作，也就是情况 1 和情况 2 交替。发现若全部都是大于 0 的，可以把 1 全推了，然后再一个一个推，最小次数即为 1 + \sum V -1。但是可能会有刚开始就进入循环的数字，那么他们要不就不推（分成散的），要不就当成 2 来做（性质），发现贡献是一样的。设 0 块的数量为 C（头尾 0 块不用算），则最小次数为 C+1+\sum V。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int ans , x;
int vis[100005];
signed main ()
{
    ios::sync_with_stdio (0) , cin.tie (0) , cout.tie (0);
    int T;
    cin >> T;
    while (T --)
    {
        int n , m;
        cin >> n >> m;
        ans = 0;
        int sq = sqrt (m);
        for (int i = 1;i <= n;i ++)
        {
            cin >> x;
            if (x == m / x) vis[i] = -1 , ans += x;
            else if (x <= sq) vis[i] = 1 , ans += m / x;
            else
            {
                vis[i] = 0;
                while (m / (m / x) != x) x = m / (m / x) , vis[i] += 2;
                ans += x;
            }
        }
        vis[n + 1] = 0;
        int mx = 0 , l = 0;
        int cnt = 0;
        vector <int> s;
        int p = 1;
        while (vis[p] == -1)p ++;
        if (vis[p] == 1) s.push_back (1);
        for (int i = 1;i <= n;i ++)
        {
            if (vis[i] % 2 == 0 && !l)
                l = i , mx = vis[i];
            else if (vis[i] % 2 == 0) mx = max (mx , vis[i]);
            else if (vis[i] == 1)
            {
                if (l) s.push_back (mx) , s.push_back (1);
                mx = 0 , l = 0;
            }
        }
        if (l) s.push_back (mx);
        if (s.size () == 0)
        {
            cout << ans << ' ' << 0 << '\n';
            continue;
        }
        int cnt0 = 0;
        for (int num : s)
        {
            if (num > 1) cnt += num - 1 , num = 1;
            else if (num == 0) cnt0 ++;
        }
        if (s[0] == 0) cnt0 --;
        if (s.size () && s[s.size () - 1] == 0) cnt0 --;
        cout << ans << ' ' << cnt + 1 + cnt0 << '\n';
    }
    return 0;
}