上海计算机学会2024年4月月赛C++乙组T1交换的轮数
发布时间
阅读量：
阅读量
交换的轮数
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个只由 0 与 1 构成序列，不断扫描序列，在每一轮扫描的过程中，如果发现有一些 1 与 0 相邻，且 1 在前，0 在后，就在这一轮扫描后，同时将这些 1 与相邻的 0 交换。不断进行调整直到将所有的 0 都在序列的前一半，所有的 1 都在序列的后一半为止。
请计算需要进行多少轮交换才能完成调整。
输入格式
- 若干 01 字符组成的一个序列
输出格式
- 单个整数：表示交换的次数。
数据范围
设 n 表示序列的长度，
- 30% 的数据，1≤n≤20
- 60% 的数据，1≤n≤5000
- 100% 的数据，1≤n≤300,000
样例数据
输入:
1100
输出:
3
解析：
对于每一个1，如果它后边有0，有几个0，就需要交换几轮；
如果它后边的1没有交换完，它只能等，如果跟后边的1紧挨着，等待的轮数为后边那个1等待的轮数+1，如果不挨着，等待的轮数为后边那个1等待的轮数减去它们俩中间0的个数，因为每个0都可以移动一轮。
最后一个1的交换轮数即为答案。
详见代码：
#include <iostream>
using namespace std;
string s;
int n;
int ans=0;
int main() {
cin>>s;
n=s.length();
int k=0;//与后边第一个1间隔多少个0
int cnt=0;//后边一共多少个0
int w=0;//等待轮数
for(int i=n;i>=1;i--){
if(s[i-1]=='0'){
cnt++;
k++;
}else{
//等待轮数为上一个1等待的轮数+1，
//如果两个1中间有0，每多一个0，少等一轮
w=w+1-k;
if (w<0) w=0;//等待轮数最小为0
if (cnt==0) w=0;//如果后边没有0，无需移动，即无需等待
//如果后边没有0，不需要动，有0计算需要多少轮，求最大值
ans=cnt+w;//前边的1一定不小于后边的1的轮数
k=0;//归零
}
}
cout<<ans;
return 0;
}
全部评论 (0)
还没有任何评论哟~