NYOJ_268_荷兰国旗问题
荷兰国旗问题
描写叙述
荷兰国旗有三横条块构成,自上到下的三条块颜色依次为红、白、蓝。现有若干由红、白、蓝三种颜色的条块序列。要将它们又一次排列使全部同样颜色的条块在一起。本问题要求将全部红色的条块放最左边、全部白色的条块放中间、全部蓝色的条块放最右边。
输入
第1行是一个正整数n(n<100),表示有n组測试数据。接下来有n行,每行有若干个由R,W,B三种字符构成的字符串序列,当中R,W和B分别表示红、白、蓝三种颜色的条块,每行最多有1000个字符。
输出
对输入中每行上由R。W。B三种字符构成的字符串序列。将它们又一次排列使全部同样颜色的条块在一起,满足前述要求。
例子输入
3
BBRRWBWRRR
RRRWWRWRB
RBRW
例子输出
RRRRRWWBBB
RRRRRWWWB
RRWB
分析:荷兰国旗问题是一个经典的题目。由于仅仅涉及到三种颜色。所以我们能够把红、白、蓝分别用1、2、3三个数字取代。能够把它看做是数组排序问题,而数组元素的值为1、2、3三种。
排好序后数组肯定分为三块区域,前部为1,中部为2,后部为3。如今我们的思路就是把未排序时前部和后部分别排在数组的前面和后面。那么中部自然就排好了。
设置两个标志位head指向数组开头。tail指向数组末尾,now从头開始遍历:
(1)假设遍历到的位置为1。那么它一定是属于前部。于是就和head交换值,然后head++,now++;
(2)假设遍历到的位置为2,说明属于中部,now++;
(3)假设遍历到的位置为3,说明属于后部,于是就和tail交换值,然而。假设此时交换后now指向的值属于前部,那么就运行(1),tail--;
事实上这个题目假设仅仅是解题的话全然不要这样子做,直接计算红、白、蓝三种颜色的数量。然后输出就可以。
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=268
代码清单:
#include<iostream>
#include<algorithm>
using namespace std; const int maxn = 100 + 5; int n;
string str;
int main(){
cin>>n;
while(n--){
cin>>str;
int len=str.size();
int now=0,ans=0;
int head=0,tail=len-1;
while(now<=tail){
if(str[now]=='R'){
swap(str[head],str[now]);
head++;
now++;
}
else if(str[now]=='W'){
now++;
}
else{
swap(str[now],str[tail]);
tail--;
}
}
cout<<str<<endl;
}return 0;
}
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
string s="RWB";
while(n--){
string str;
cin>>str;
int ans[3]={0};
int len=str.size();
for(int i=0;i<len;i++){
if(str[i]=='R') ans[0]++;
else if(str[i]=='W') ans[1]++;
else ans[2]++;
}
for(int i=0;i<3;i++){
for(int j=0;j<ans[i];j++){
cout<<s[i];
}
}cout<<endl;
}return 0;
}
最新文章
- A Beginner&#39;s Guide to Paxos
- mysql在同一个表上查询和更新
- VS2012下配置MPI
- Oracle shutdown immediate遭遇ORA-24324 ORA-24323 ORA-01089
- Scikit-Learn模块学习笔记——数据预处理模块preprocessing
- 转】MyEclipse使用总结——使用MyEclipse打包带源码的jar包
- Shoot the Bullet
- randn命令中randn(&#39;state&#39;)和randn(&#39;seed&#39;)的不同
- Golang之Context的使用
- Django-6 Django ORM层
- Shell 编程注意点
- 小程序引入百度api天气预报
- Confluence 6 已经存在的 Confluence 安装配置一个数据源连接
- python 可迭代对象
- 接口测试-webservice接口---soapui
- gpexpand分析
- 阿里八八Alpha阶段Scrum(1/12)
- CSUOJ 1901 赏赐 OR 灾难 单调栈
- Objective-C的属性和成员变量用法及关系浅析
- JavaScript中的BOM知识框架
热门文章
- 将DataTable某一列的值整体赋值给 另一个DataTable
- Java算法——求出两个字符串的最长公共字符串
- matplotlib之pyplot 知识点滴
- js基础标签用法
- python爬虫:找房助手V1.0-爬取58同城租房信息
- MatLab之Simulink之simple model
- Memcached 之增删改查命令
- C#连接Oracle数据库的方法(System.Data.OracleClient、Oracle.DataAccess.Client也叫ODP.net、Oracle.ManagedDataAccess.dll)
- BZOJ 3943: [Usaco2015 Feb]SuperBull 最小生成树
- Spring Cloud Alibaba、Spring Boot、Spring Cloud对应版本关系