Codeforces Round 910 (Div. 2)

基本情况

做A题的速度比之前快多了，大概20分钟搞定。

B题想了一个贪心错解，想用链表实现，但是不熟练，实现太慢，而且还被hack了。

但是自己hack掉了，造数据上进步。

B. Milena and Admirer

贪心思路

发现一个大于下一个的数，直接对半分，如果不能对半就小的在前大的在后。

分完之后用链表先删除当前数，再插入两个新的数，然后再跑一次新的数列。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <list>

using namespace std;

int n;
list<long long> a;
long long temp;

void solve()
{
	long long ans = 0;
	while (true)
	{
		int cnt = 0;
		auto tp = a.begin();
		long long temp = *tp;
		tp++;
		for (auto p = tp; p != a.end(); p++)
		{
			if (*p > temp)
			{
				temp = *p;
				if (temp % 2 == 0)
				{
					p = a.erase(p);
					p = a.insert(p, {temp / 2, temp / 2});
				}
				else
				{
					p = a.erase(p);
					p = a.insert(p, {temp - temp / 2, temp / 2});
				}
				cnt++;
			}
			else
			{
				temp = *p;
			}
		}
		ans += cnt;
		if (cnt == 0)
		{
			break;
		}
	}
	cout << ans << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T;
	cin >> T;
	while (T--)
	{
		a.clear();
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> temp;
			a.push_front(temp);
		}
		solve();
	}
	return 0;
}

光是实现这个错解就满头大汗了。

因为指针操作不熟练，一开始我对删除加入新元素的操作是这样实现的

a.erase(p);
a.insert(p, {temp / 2, temp / 2});

然后导致各种异常，因为第一个操作过后\(p\)指针指向的东西都被删除了，不能直接\(p\)那边插入，这跟数组下标不一样。而是通过这类函数都会返回的操作完的指针位置来定位下一步操作的指针位置。

p = a.erase(p);
p = a.insert(p, {temp / 2, temp / 2});

HACK

然而这是错解。

我发现了一组数据

3
2 6 2

这组数据如果按照我的解法

2 6 2\\0
2 3 3 2\\1
2 1 2 1 2 2\\3
1 1 1 1 1 1 2 2\\5

而最优解却是

2 6 2\\0
2 2 4 2\\1
2 2 2 2 2\\2

然而只剩5分钟结束了。

正确贪心

思路

正解是贪心没错。

目标性更强，当发现一个大于后面元素的数之后，操作的目的是让这个数变得尽可能等于后面那个数。

即\(\lceil \frac{a_{i-1}}{k} \rceil \leq a_i\)

变换一下，就是找出 \(k=\lceil \frac{a_{i-1}}{a_i} \rceil\)

那么答案加上 \(k - 1\)，因为分成 \(k\) 分 只要操作 \(k-1\) 次。

然后把当前这个数设置为 \(\lfloor \frac{a_{i-1}}{k} \rfloor\) ，即均分为\(k\)个之后的最小部分，来保证之后算法的正确性。

用这个算法来操作刚才的 hack 数据。

2 6 2\\0
6 / 2 = 3
ans += 3 - 1;
2 2 2\\2

确实正确。

实现

然而实现也没那么舒服，我一开始没有彻底理解这个做法，导致答案始终出错。

这是一开始的代码

for (int i = 2; i <= n; i++)
{
	int k = getUpper(a[i - 1], a[i]); 
	ans += k - 1;
	a[i - 1] /= k;
}

问题在于，我的\(a[i - 1]\)是为了保证之后答案的正确性才取了分割后的最小部分，但是顺着枚举下一次根本用不到\(a[i - 1]\)，顺序改一下就过了。

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;
using li = long int;

const int N = 2e5 + 10;
li a[N],n; 

li getUpper(li a, li b)
{
	if (a % b == 0)
	{
		return a / b;
	} else {
		return a / b + 1;
	}
}

int main()
{
	int T;
	li ans;
	cin >> T;
	while(T--)
	{
		cin >> n;
		ans = 0;
		for (int i = 1; i <= n; i++)cin >> a[i];
		for (int i = n - 1; i >= 1; i--)
		{
			int k = getUpper(a[i], a[i + 1]); 
			ans += k - 1;
			a[i] /= k;
		}
		cout << ans << endl;
	}
	return 0;
}