AtCoder Beginner Contest 166 F Three Variables Game 中庸之道

AtCoder Beginner Contest 166   比赛人数11690  比赛开始后11分钟看到所有题

AtCoder Beginner Contest 166  F  Three Variables Game   中庸之道

总目录详见https://blog.csdn.net/mrcrack/article/details/104454762

在线测评地址https://atcoder.jp/contests/abc166/tasks/abc166_f

思路：

1.若当前两字母数量不等，让数量多的减1，数量少的加1.可以这样考虑，因测试数据是随机生成，之后的数据，遇到两字母的概率应该均等，故采用中庸之道，让两者数量尽量接近。

2.若当前两字母数量相等,考虑让接下来马上要用到的加1(因为只有3个字母,所有一定会有一个字母,接下来马上用到),另一个减1

3.若当前需要减1的数量是0,那么输出No.

样例模拟如下

Input:
8 6 9 1
AC
BC
AB
BC
AC
BC
AB
AB
Output:
Yes
C
C
A
C
C
C
B
A8 6 9 1
AC
6>1 6-1=5,1+1=2,输出C   当前A,B,C数量5,9,2BC
9>2 9-1=8,2+1=3,输出C   当前A,B,C数量5,8,3AB
5<8 8-1=7,5+1=6,输出A   当前A,B,C数量6,7,3BC
7>3 7-1=6,3+1=4,输出C   当前A,B,C数量6,6,4AC
6>4 6-1=5,4+1=5,输出C   当前A,B,C数量5,6,5BC
6>5 6-1=5,5+1=6,输出C   当前A,B,C数量5,5,6AB
5==5 接下来马上会用到B 让B加，A减，5-1=4,5+1=6,输出B   当前A,B,C数量4,6,6AB
4>6 6-1=5,4+1=5,输出A   当前A,B,C数量5,5,6

AC代码如下

#include <cstdio>
#include <algorithm>
#define maxn 100010
using namespace std;
char in[3];
int n,v[3],p[maxn],q[maxn],ans[maxn];
int main(){int i;scanf("%d",&n);for(i=0;i<3;i++)scanf("%d",&v[i]);//v[0]代表'A'的数量,v[1]代表'B'的数量,v[2]代表'C'的数量for(i=1;i<=n;i++)scanf("%s",in),p[i]=in[0]-'A',q[i]=in[1]-'A';for(i=1;i<=n;i++){if(v[p[i]]>v[q[i]])swap(p[i],q[i]);//让v[]小的在前else if(v[p[i]]==v[q[i]]){if(i+1<=n&&(q[i]==p[i+1]||q[i]==q[i+1]))swap(p[i],q[i]);//让接下来马上要用到的,在前}if(!v[q[i]])return 0*printf("No\n");v[p[i]]++,v[q[i]]--,ans[i]=p[i];}printf("Yes\n");for(i=1;i<=n;i++)printf("%c\n",'A'+ans[i]);return 0;
}

该题总体印象，数据弱，很多代码虽能AC,但贪心正确与否，还是值得商榷的。