2020 牛客暑假训练营补题 (第八场)
暑假还是不能摸鱼了,尽量每天补一道题。
这里大部分的补题应该都是参考了大佬的题解,所以如果有大佬看到了自己的解法,请多多包涵。
I题
题目描述
这道题的意思是给你一个N表示接下来给的数据组数。每组数据有a和b,每一轮需要处理一组数据。
每一轮能进行以下三种操作的其中一种:
- 什么也不做;
- 如果其中的a在之前没有被选择过,选择a;
- 如果其中的b在之前没有被选择过,选择b。
这里的没有被选择过是指作为a被选和作为b被选。
试求出最大的选择的次数。
题目思路
开始做这道题理解错了意思,以为选择的条件是选择a的话之前它没有作为a选择过就行。这样写出来的初步代码示例答案都对不上。
然后想着先把这些数据排序,再按“之前没有被选过,之后没有相同数据就无脑选”的方法做。发现有些特殊情况不能过。
最后看题解才知道是要把这些数据放在图中,如果一些数据形成环则选择数量加上环的边数,如果没有成环那就是图的边数-1。
代码
还有一点没完善……明天应该差不多了。