一道渡口模拟题
一个港口上有N辆车排队，有卡车和货车，用0代表卡车，1代表货车，现在有如下规则，当同类型的车排队时，先来的车在前面，而卡车和货车来时，卡车先，除了以上规则外，还有如下规则：当有4辆卡车时，必须有一辆货车，当没有货车时，卡车可以排上，当卡车不到4量时，可以用货车补上，下面是一个例子
7
输入：0 0 1 0 1 0 0
输出：0 1 3 5 2 6 4
下面讲下思路：
对于输入我们可以编号，从0开始：
输入：0 0 1 0 1 0 0
编号：0 1 2 3 4 5 6
此时，可以先对同样的0和1进行排序，要稳定排序，此时可以使用基数排序
排序：0 0 0 0 0 1 1
编号：0 1 3 5 6 2 4
接着按照规则每4个0有个1开始排序
0 0 0 0 0 0 0 1 1 1 1 1 1 1
| |
index0 index1
index0和index1分别往后移动，移动规则如下：
每碰到4个0，排一个1
原数组：0 0 0 0 0 0 0 1 1 1 1 1 1 1
输出： 0 0 0 0 1 0 0 0 1 1 1 1 1 1
如果还有不明白的可以配合代码看下：
#include <iostream>#include <vector>#include <map>using namespace std;int main(){int N;/**/cin >> N; // 输入总车数vector<int> vec;vector<int> seq;seq.resize(N);vec.resize(N);int ke,huo;ke = huo = 0;for ( int i=0; i<N; ++i ){int num;cin >> num;vec[i] = num;if ( num == 0 )ke++;elsehuo++;}int index1 = N;int index0 = ke;for ( int i=N-1; i>=0; --i ) // 基数排序，稳定排序{if ( vec[i] == 1 )seq[--index1] = i;else seq[--index0] = i;}// 如今 seq中保存了下标vector<int> ret;ret.resize(N);int k,i,j;k = 0; // i表示卡车开始坐标，j表示货车开始 for ( i=0,j=ke; i<ke && j<N; ){ret[k++] = seq[i++];if ( k % 4 == 0 ) // 每4个0，一个1ret[k++] = seq[j++];}while ( i < ke )ret[k++] = seq[i++];while ( j < N )ret[k++] = seq[j++];for ( int i=0; i<N; ++i )cout<<ret[i]<<" ";cout<<endl;}