c++代码幼儿园有 N 个孩子玩游戏,随机围成了一个圈,老师最终想让所有男生排列到一起,所有女生排列到一起。每次老师可以命令两个孩子交换位置,求最小的命令次数
时间: 2023-09-15 07:05:42 浏览: 112
一个免费的c++小游戏集合
5星 · 资源好评率100%
### 回答1:
这是一道交换给定的字符串的指定子串的顺序的问题。
具体来说,我们可以将这个问题转化为交换男生和女生的子串的顺序。
首先,我们可以找出男生和女生的子串的起始位置。然后,我们可以通过计算男生和女生的子串的长度来确定最小的命令次数。
例如,假设我们有一个字符串 "NNMNMNMNN",其中 "N" 代表男生,"M" 代表女生。
那么,我们可以将它转换为 "NNNNNNMMM",其中 "N" 和 "M" 之间的距离为 6。
因此,我们可以得出答案为 6。
代码实现如下:
```
int minCommands(string s) {
int n = s.size();
int startN = -1, startM = -1;
for (int i = 0; i < n; i++) {
if (s[i] == 'N') {
startN = i;
break;
}
}
for (int i = 0; i < n; i++) {
if (s[i] == 'M') {
startM = i;
break;
}
}
return abs(startN - startM);
}
```
注意:如果男生或女生的子串不存在,则应返回 0。
### 回答2:
这道题可以使用环形链表的思想来解决。
首先,遍历链表,统计男生和女生的数量,设男生数量为n1,女生数量为n2。
接下来,我们需要将男生和女生全部排列在一起。为了尽量减少交换的次数,我们可以找出男生数量和女生数量中的较小值作为基准,将基准数的孩子排列在一起,然后将剩余的孩子依次插入到基准数的两侧。
假设n1为男生数量,n2为女生数量,令m为min(n1, n2)。我们首先将第一个男孩和第一个女孩交换位置,然后将第一个男孩和第m+1个女孩交换位置,然后将第一个男孩和第2m+1个女孩交换位置,依次类推,直到将所有的男孩都交换到一起。
此时,我们得到了一个链表,其中男孩和女孩分别排列在一起,但是可能存在一部分男孩和女孩的顺序没有按照老师的要求排列到一起。
然后,我们需要继续交换男孩和女孩之间的位置,直到所有男孩排在一起,这部分男孩的数量为n1-m。同理,我们也需要将女孩排在一起,女孩的数量为n2-m。
最后,我们需要计算交换的次数。由于每次交换需要交换两个孩子的位置,因此,我们需要交换的次数等于n1-m+n2-m。
综上所述,最小的命令次数为n1-n2的绝对值加上min(n1,n2)-max(n1,n2)。
### 回答3:
首先,我们需要确定男生和女生的分布情况。遍历整个圈,计算男生和女生分别的数量,然后根据数量多少,确定男生和女生的位置。假设男生人数为m,女生人数为n。
接下来,我们需要将男生和女生分别排列到一起。考虑到每次只能命令两个孩子交换位置,那么我们可以使用冒泡排序的思想来解决这个问题。
对于男生的位置,我们可以从圈中的第一个孩子开始,向后遍历直到找到一个女生为止。在这个过程中,我们可以记录交换位置的次数。将找到的女生与当前位置的男生交换位置,并将交换次数加1。然后继续遍历圈中的下一个孩子,直到所有的男生都排在一起。
对于女生的位置,我们同样可以从圈中的第一个孩子开始,向后遍历直到找到一个男生为止。在这个过程中,我们同样可以记录交换位置的次数。将找到的男生与当前位置的女生交换位置,并将交换次数加1。然后继续遍历圈中的下一个孩子,直到所有的女生都排在一起。
最后,将男生排列好的位置和女生排列好的位置的交换次数相加,即为最小的命令次数。
根据上述思路和算法,可以求得最小的命令次数。
阅读全文