三色旗问题

问题描述

假设有一条绳子,上面有红、白、蓝三种颜色的旗子,起初绳子上的旗子的颜色并没有顺序,你希望将之分类并排列为蓝、白、红的顺序,要如何移动次数最少,注意你只能在绳子上进行这个动作,并且一次只能调换两个旗子。

解决思路

快排的思想,分别设三个标记wflag,rflag,bflag,初始bflag和wflag置首,rflag置末,然后分以下几个步骤解决:

  1. rflag向左移动到第一个非红色旗处停下,bflag向前移动到第一个非蓝色旗停下,wflag向前移动超越bflag并在非白色旗处停下
  2. wflag处如果为红旗则与rflag处的旗交换位置,如果为蓝旗则与bflag处的旗交换位置,交换位置后移动更新三个标志位的位置
  3. 重复1~2步直到wflag > rflag

具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

//char color[] = {'r','w','b','w','w','b','r','b','w','r','\0'};
char color[] = {'r','r','r','r','r','b', '\0'};
int n = strlen(color);
int wflag = 0, bflag = 0, rflag = n - 1;

void move() {
while (bflag < n && color[bflag] == 'b') bflag++;
while (wflag < n && (wflag < bflag || color[wflag] == 'w')) wflag++;
while (rflag >= 0 && color[rflag] == 'r') rflag--;
}

int main()
{
int res = 0;
cout << color << " " << n << endl;
move();
while (wflag < n && wflag <= rflag) {
if (color[wflag] == 'r') {
swap(color[wflag], color[rflag]);
res++;
} else if (color[wflag] == 'b') {
swap(color[wflag], color[bflag]);
res++;
}
move();
}
cout << color << endl;
cout << "至少交换 " << res << " 次" << endl;
return 0;
}
---------------- The End ----------------

作者: brooksjay
联系邮箱: jaypark@smail.nju.edu.cn
本文地址: https://brooksj.com/2019/08/14/三色旗问题/
本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
转载请注明出处, 谢谢!