Codeforces Round #734 (Div. 3) C. Interesting Story (贪心)

题目链接

题意

给定 \(n\) 个只含 \(a\) 到 \(e\) 的字符串,求最多能选出多少个字符串,使得存在某个字母出现次数严格大于其它字母。

分析

首先我们看下数据范围,2e5的然后\(a-e\)只有5个字符,所以我们可以贪心的想,就是把符合的提取出来就行了,严格大于其他字符是说,某一字符数量大于其他字符数量和。

然后我们看,同一个串中某一字符比其他字符多多少,字符长度为len,当前字符长度为x那么当前字符比其他字符多\(x*2-len\),就是其他字符数量为\(len-x\),\(x-(len-x)\).

之后排序贪心选代价大于0求出最多能选多少个。

void solve(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		for(int j=0;j<5;j++){
			num[i][j]=0;
		}
	}
	
	for(int i=1;i<=n;i++){
		cin>>str;
		for(int j=0;j<(int)str.size();j++){
			++num[i][str[j]-'a'];
		}
		for(int j=0;j<5;j++){///jiazhi
			ans[j][i]=2*num[i][j]-str.size();
		}		
	}
	
	ll res=0;
	for(int i=0;i<5;i++){
		sort(ans[i]+1,ans[i]+n+1);
		ll a,b;
		a=b=0;
		for(int j=n;j>0;j--){
			if(b+ans[i][j]>0) {
				b+=ans[i][j];
				++a;
			}
			res=max(res,a);
		}
	}
	printf("%lld\n",res);
	
}
上一篇:Redhat Cluster Suite原理介绍


下一篇:轻轻学爬虫—scrapy框架巧用8—猴子偷桃(4)