CodeForces 922D Robot Vacuum Cleaner 排序

388人浏览 / 3人评论

题目链接

  • Robot Vacuum Cleaner
    • 这一题需要抓住产生“sh”字符串的本质思考,否则茫然无所措。
    • 我们首先想到统计每个字符串内分别有多少‘s’和‘h’(分别存在s_num和h_num数组中),为下面的贪心做准备。
    • 每个字符串自身含有的“sh”数目是固定的,与它们的顺序无关,我们考虑字符串排列顺序时不予考虑。
    • 考虑任意两个字符串a和b:我们知道如果a在b前,那么会产生s_num[a]*h_num[b]个“sh”;反之如果b在a前,则会产生s_num[b]*h_num[a]个“sh”。显然我们需要取大的那一种。
    • 所以得出排序规则:a在b前 <=> s_num[a]*h_num[b]>s_num[b]*h_num[a]。
    • 将所有字符串按以上规则排序即可得到最优序列,然后统计答案即可。
    • 统计答案方法:ans初始化为0,遍历最有字符串,记录前面出现‘s’的数量,每逢‘h’则ans加上前面‘s’的数量。

代码:

#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int snum[(int)1e5+10],hnum[(int)1e5+10],Index[(int)1e5+10];
bool cmp(int a,int b)
{
	return snum[a]*(long long)hnum[b]>snum[b]*(long long)hnum[a];
}
int main()
{
	int n;
	scanf("%d",&n);
	string*s=new string[n];
	for(int i=0;i<n;++i)
	{
		Index[i]=i;
		cin>>s[i];
		int len=s[i].size();
		for(int j=0;j<len;++j)
		{
			if(s[i][j]=='s')
			{
				++snum[i];
			}
			else
			{
				++hnum[i];
			}
		}
	}
	sort(Index,Index+n,cmp);
	long long ans=0,s_tmp=0;
	for(int i=0;i<n;++i)
	{
		int len=s[Index[i]].size();
		for(int j=0;j<len;++j)
		{
			if(s[Index[i]][j]=='s')
			{
				++s_tmp;
			}
			else
			{
				ans+=s_tmp;
			}
		}
	}
	printf("%lld",ans);
	return 0;
}

全部评论