cf749C

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog

cf749C

链接

题意

        共有n个人,编号为1~n。他们每个人属于且仅属于R阵营或N阵营中的一个。现在他们要进行一场投票。投票可能进行多轮,每一轮投票都是按照从1~n的顺序,当轮到某一人投票的时候,他可以什么都不做,也可以随便挑选一人使他丧失投票的权利。每个人都会代表自己阵营的利益。一个人如果丧失了投票权利,则他直到这场投票结束都不能再投票。投票直到某一阵营一个人都没有的时候就会结束,此时一个人都没有的阵营失败,另一个阵营获胜。
        
        现在给定每个人所属的阵营,问最后哪个阵营会获胜。
        要求线性时间解决

题解

        贪心做法:
            每个人干掉他后面的第一个非本阵营的人即可,模拟一下