题目大意

给你一个

n

个浮板，小 S 每次操作可以用

i

的代价把第

i

个浮板翻面，同时所有

j\le i

的浮板会移动到

j-1

的位置，然后小 Y 会把

0

号位上的浮板不翻面地挪到

i

号位上，求把所有浮板变成同一面朝上的最小代价。

思路

本题考察贪心。

先只考虑全部翻成反面朝上的情况。

因为每次操作都会且仅会使一个浮板翻面，所以把原来就是反面的浮板翻掉肯定不是最优的。同时，如果对第

i

个位置的浮板操作一次，那么满足

j<i

的所有浮板都会往前移，当再去翻前面这些些浮板的时候，所需的代价就会减一。所以要优先把后面的浮板翻掉，使可以减少的代价最多。

从后往前贪心，若第

i

个位置是

0

，那直接忽略。否则要把当前位置变成

1

。这时，先确保第

1

个浮板是反面（不然就对它操作一次，把它变成反面），然后对第

i

个浮板操作一次，使之变成反面朝上。

举个栗子，样例里的 1011100 会经历如下过程

1011100->0011100->0110000->1000000->0000000

ans=1+5+3+1=10

全部翻成正面朝上的情况同理，然后把算出来的两个答案取

\min

即可。

Code

如果暴力模拟这个过程，那么 T 飞了，时间复杂度是

O(n^2)

的，期望只有 60 pts 。

但是我们可以使用嘿科技 deque 来模拟，这样把时间复杂度降到了

O(n)

，然后就可以愉快地 AC 这道题了。

最后，十年 OI 一场空，不开 _ _ 见祖宗！

CPP

#include <bits/stdc++.h>

using namespace std;
const int N = 1145140;

#define endl '\n'
#define int long long //防止溢出

deque <char> q; //STL niubi!!!
string s;
int n;

void solve() {
	cin >> n;
	cin >> s;
	for (int i = 0; i < n; i++) q.push_back(s[i]);
	int ans1 = 0, ans2 = 0;

	while (!q.empty()) {
		if (q.back() == '1') {
			if (q.size() == 1) {
				ans1++;
				q.pop_back();
				break;
			} //特判一下，防止RE
			ans1 += q.size();
			if (q.front() == '1') ans1++;//确保第一个浮板是反面
			q.pop_front();
			q.pop_back();
		} else q.pop_back();
	} //全部翻成反面朝上

	for (int i = 0; i < n; i++) q.push_back(s[i]);

	while (!q.empty()) {
		if (q.back() == '0') {
			if (q.size() == 1) {
				ans2++;
				q.pop_back();
				break;
			} //特判一下，防止RE
			ans2 += q.size();
			if (q.front() == '0') ans2++;//确保第一个浮板是正面
			q.pop_front();
			q.pop_back();
		} else q.pop_back();
	}//全部翻成正面朝上

	cout << min(ans1, ans2);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		solve();
		cout << endl;
	}//多测
	return 0;
}

题解——P14258 好感（favor）

文章操作

题目大意

思路

Code

相关推荐

评论

题解——P14258 好感（favor）