题解：P8080 [COCI 2011/2012 #4] KINO

lailai0916 · 2022-01-28 18:51:49 · 题解

题意简述

一排 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)。

参考代码

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