P13009

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

当 $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$ 例外，需特判）。
当 $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

CPP

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

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

文章操作

P13009

AC Code

相关推荐

评论

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