专栏文章

题解：P14258 好感（favor）

GGhostcoder
P14258题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minjl2sr
此快照首次捕获于
2025/12/02 03:28
3 个月前
此快照最后确认于
2025/12/02 03:28
3 个月前
查看原文
这里提供一个简单易懂的贪心+模拟方法。

思路

使用模拟的思路很简单。
因为把所有浮板翻成正面朝上和反面朝上使用的思路相同，所以这里以把所有浮板都翻成 chch 为例，其中 chch 为目标字符（00 或 11）。
那么我们要怎样才能保证移动的距离总和最小呢？
首先注意到如果翻了最后一个 chch，那么前面的所有 chch 都会向前移动一个单位，这样总的最终距离会缩短很多，当然是最贪心的思路。
但是是不是所有时候都可以将最后一个 chch 进行翻面呢？当然不是。如果当前最前面的字符是 chch，那么翻动最后面的 chch 时，最前面的 chch 就会非常难受的移到最后一个 chch 的后面，这样当然就不能保证最优了!
所以，最终的贪心方法是：
  • 当最前面的字符为 chch 时，将它先翻面。
  • 最前面的字符不是 chch 时，翻动最后一个 chch。
由于每翻动一次浮板，影响到的是前面和自身的所有浮板，所以考虑使用两个指针 l,rl,r 分别指向最前面和最后面的目标字符进行模拟，类似于双指针。

初始化

输入字符串 ss 时先在前面加上一个空格，使下标从 11 开始，方便后面的处理。
指针 ll 开始是 11，因为要从开头开始模拟。指针 rr 需要找到最后一个 chch，那么我们可以直接遍历找最后一个 chch，如果没找到就返回极大值表示不能将所有浮板都翻成 chch 朝上的状态。

开始模拟

我们使用一个 while 循环，当两个指针 l,rl,r 没有在同一点上时持续模拟。
首先考虑指针 ll 所处位置的字符是否是 chch。如果是，那么要先翻动它，移动距离为 11，并且我们要标记这个字符已经计算过了，标记为任意一个不为 0,10,1 的字符。
再考虑指针 rr 所处位置的字符是否是 chch。如果是，那么就翻动它，移动的距离为 r−l+1r-l+1。这里有个细节，就是翻动最后一个 chch 造成前面移动一个单位的这个移动不需要模拟出来，因为这个移动会把最前面的字符移到最后面的 chch 的后面，也就等同于把最前面的指针 ll 加了 11。这样处理就可以避免模拟大量的移动，从而减少时间复杂度了。
循环的每一次，rr 都要减 11 来往前面找。
最后返回累加的移动时间就是将所有浮板翻动成 chch 朝上所需要的时间。答案的话就是翻成正面和反面所需时间的最小值了。时间复杂度为O(T×n)\mathcal{O}(T\times n)。

代码解决

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n;
string s;
int count(string s,char ch){
	int l=1,r=-1,ans=0;
	for(int i=1;i<=n;i++)if(s[i]==ch)r=i;
	if(r==-1)return 1e9;
	while(l<=r){
		if(s[l]==ch){
			ans++;
			s[l]='#';
		}
		if(s[r]==ch){
			ans+=(r-l+1);
			l++;
		}
		r--;
	}
	return ans;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>s;
		s=" "+s;
		cout<<min(count(s,'1'),count(s,'0'))<<"\n"; 
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...