三色旗问题

问题描述

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

解决思路

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

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

具体实现

#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;
}