璟雯院

珺璟如晔,雯华若锦

用户工具

站点工具


icpc:problems:usaco23jan_leaders_b
problems
名称Leaders B
题目编号USACO23JAN_B1
题目链接luogu.com.cn/…
来源USACO
算法分类特判, 思维
难易程度容易

Leaders B

想法

找到第一个G,最后一个G,第一个H,最后一个H。只有第一个H与G可能满足条件1。如果满足条件1,则可以将范围内的相反牛作为领袖,如果不满足,则查看第一个相反牛是否可以作为领袖。

代码实现

#include<cstdio>
const int N = 2*1e5+10;
char line[N];
int E[N];
int n;
 
int main()
{
	scanf("%d", &n);
	scanf("%s", line+1);
	for(int i=1; i<=n; i++)
		scanf("%d", &E[i]);
 
	int f_G = 1, l_G = n, f_H = 1, l_H = n;
	while(line[f_G] != 'G') f_G++;
	while(line[f_H] != 'H') f_H++;
	while(line[l_G] != 'G') l_G--;
	while(line[l_H] != 'H') l_H--;
 
	int ans = 0;
	if(E[f_G] >= l_G)
		for(int i=1; i<=f_G; i++)
			if(line[i] == 'H' && E[i] >= f_G)
				ans++;
	else if(E[f_G] < f_H)
		ans++;
 
	if(E[f_H] >= l_H)
		for(int i=1; i<=f_H; i++)
			if(line[i] == 'G' && E[i] >= f_H)
				ans++;
	else if(E[f_H] < f_G)
		ans++;
 
	printf("%d", ans);
	return 0;
}
/app/www/public/data/pages/icpc/problems/usaco23jan_leaders_b.txt · 最后更改: 2023/05/23 11:15 由 温婕莺