题面

现有两个厕所，一个女士专用，一个通用，给出\(2*n\)个排成一列的人的性别

每人如厕需要一分钟，假如女厕是空的，女生中最靠前的可以直接进入。

需要通过调换顺序使得所有人都上完厕所最后的时间为n分钟

要求最小化队伍中更改位置的最远距离

题目范围戳这里

题解

考虑不合法的情况：

一定是当前状态下还在等待的男生比女生多两个以上（多一个时，肯定通用厕所是空的）

那么

设男生贡献为1，女生为-1，所以我们要保证任何时候序列总和<2，即：任意后缀和 < 2

然后考虑如何贪心？？？

在贪心之前，我们先找出几个可贪心的性质：

对于第一个女生来说，她向后挪了一个位置，则一定有一个男生插队在其之前，挪了两个就是两个男生插队

而我们可以发现

对于同性的人来说，相对顺序是不会变的（即使有男生插队，同性别个体相同，所以相对顺序还是不变）

所以我们可以得到一个妙妙的结论：

除去开头的男生，无论哪个位置的多少个男生移到最前列，所产生的贡献一定是男生的数量

我们略加思考就可以想到：

在排除男生总数多于女生之后，

对于一个有冲突的男生（即加上此人男生正好比女生多2），我们肯定需要改变他的位置

而他前移过程中超过的每个女生都会产生1的贡献，我们只要求最小化最大的女生移动距离

所以我们将当前这个有冲突的男生移到最前面一定是最优的，因为将其移到最前端之后他不可能再产生贡献

所以思路就很清晰了，直接统计有多少个需要挪动的男生就好

关于如何统计：

对于每个给定的字符串Si 分别统计总和\(sum_i\)
记录 Si 求后缀时产生的最大值\(maxx_i\)
当这个字符串Si 接入整体时，它的贡献就是：

(k[i]-1)*sum[i]+maxx[i]
因为贡献不会是负数（男生不能向后挪）所以当 sum[i]<2 时，贡献为： maxx[i]

代码

#include<bits/stdc++.h>

using namespace std;

#define re register

#define in inline

#define ll long long

#define get getchar()

in ll read()

{

    ll t=0,x=1;char ch=get;

    while((ch<'0'||ch>'9')&&ch!='-')ch=get;

    if(ch=='-')x=-1,ch=get;

    while(ch<='9'&&ch>='0')t=t*10+ch-'0',ch=get;

    return x*t;

}

const int _=2e5+5;

char s[_];

int sum[_],maxx[_];

ll k[_],tot,ans=1;

int main()

{

    ll n=read(),m=read();

    for(re int i=1;i<=m;i++)

    {

	scanf("%s",s+1);

	k[i]=read();

	int len=strlen(s+1);

	for(re int j=len;j>=1;j--)

	{

            int flag=(s[j]=='M'?1:-1);

	    sum[i]+=flag; //统计总和

	    maxx[i]=max(maxx[i],sum[i]); //统计当前字符串的后缀最大值

	}

    }

    for(re int i=m;i>=1;i--)

    {

	if(sum[i]>0) //说明当前这节中男生多了

	    ans=max(ans,tot+1LL*sum[i]*(k[i]-1)+maxx[i]); //本段中要挪动的男生数量

	else //尽管男生总体不多，但是可能存在与下一段接洽的地方男生多了（因为每段要重复多次）

	    ans=max(ans,tot+maxx[i]);

	tot=tot+1LL*sum[i]*k[i];

    }

    if(tot>1) cout<<"-1"<<endl;

    else cout<<ans-1<<endl;

    return 0;

}

巴特西

LuoguP3615 如厕计划

题面

题解

考虑不合法的情况：

设男生贡献为1，女生为-1，所以我们要保证任何时候序列总和<2，即：任意后缀和 < 2

然后考虑如何贪心？？？

对于第一个女生来说，她向后挪了一个位置，则一定有一个男生插队在其之前，挪了两个就是两个男生插队

对于同性的人来说，相对顺序是不会变的（即使有男生插队，同性别个体相同，所以相对顺序还是不变）

除去开头的男生，无论哪个位置的多少个男生移到最前列，所产生的贡献一定是男生的数量

所以我们将当前这个有冲突的男生移到最前面一定是最优的，因为将其移到最前端之后他不可能再产生贡献

关于如何统计：

代码

最新文章

热门文章

巴特西

LuoguP3615 如厕计划

题面

题解

考虑不合法的情况：

设男生贡献为1，女生为-1，所以我们要保证任何时候 序列总和<2，即： 任意后缀和 < 2

然后考虑如何贪心？？？

对于第一个女生来说，她向后挪了一个位置，则一定有一个男生插队在其之前，挪了两个就是两个男生插队

对于同性的人来说，相对顺序是不会变的（即使有男生插队，同性别个体相同，所以相对顺序还是不变）

除去开头的男生，无论哪个位置的多少个男生移到最前列，所产生的贡献一定是男生的数量

所以我们将当前这个有冲突的男生移到最前面一定是最优的，因为将其移到最前端之后他不可能再产生贡献

关于如何统计：

代码

最新文章

热门文章

设男生贡献为1，女生为-1，所以我们要保证任何时候序列总和<2，即：任意后缀和 < 2