P8080题解

题意简述

一排 $n$ 个座位，普通座位 $\texttt S$ 与成对出现的爱心座位 $\texttt L$。相邻座位之间、以及整排两端都有杯架，唯独同一对爱心座位之间没有。$n$ 人坐满，每人用左侧或右侧的一个杯架，每个杯架至多供一人使用，求最多多少人能用上杯架。

解题思路

数杯架总数。座位间的缝加上两端共 $n+1$ 处，每对爱心座位内部少一个杯架，记 $\texttt L$ 的个数为 $l$，则爱心对数为 $l/2$，杯架总数为 $n+1-l/2$。

座位与相邻杯架排成一条链，从左到右每个座位优先取左侧的空杯架、否则取右侧，总能用满 $\min(\text{杯架数},n)$ 个。故答案为 $\min\left(n+1-\frac l2,n\right)$。

时间复杂度为 $O(n)$。

参考代码

218 Bcpp

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	string s;
	cin>>n>>s;
	int l=count(s.begin(),s.end(),'L');
	cout<<min(n+1-l/2,n)<<'\n';
	return 0;
}