Description
You have to reorder a given bit string as specified. The only operation allowed is swapping adjacent bit pairs. Please write a program that calculates the minimum number of swaps required. The initial bit string is simply represented by a sequence of bits, while the target is specified by a run-length code. The run-length code of a bit string is a sequence of the lengths of maximal consecutive sequences of zeros or ones in the bit string. For example, the run-length code of “011100” is “1 3 2”. Note that there are two different bit strings with the same run-length code, one starting with zero and the other starting with one. The target is either of these two. In Sample Input 1, bit string “100101” should be reordered so that its run-length code is “1 3 2”, which means either “100011” or “011100”. At least four swaps are required to obtain “011100”. On the other hand, only one swap is required to make “100011”. Thus, in this example, 1 is the answer.
Input
The input consists of several tests case. For each test, the test case is formatted as follows. NM b1 b2 ...bN p1 p2 ...pM ThefirstlinecontainstwointegersN (1≤N ≤15)andM (1≤M ≤N). Thesecondline specifies the initial bit string by N integers. Each integer bi is either 0 or 1. The third line contains the run-length code, consisting of M integers. Integers p1 through pM represent the lengths of consecutive sequences of zeros or ones in the bit string, from left to right. Here, 1≤pj for1≤j≤M and Mj=1pj =N hold. Itisguaranteedthattheinitialbitstringcanbe reordered into a bit string with its run-length code p1, . . . , pM .
Output
Output the minimum number of swaps required.
Sample Input
6 3 1 0 0 1 0 1 1 3 2 7 2 1 1 1 0 0 0 0 4 3 15 14 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 0 1
Sample Output
1 12 7 0
Hint
题意：给一个字符串，移动最少次数，使得该字符串中的字符满足给定条件
思路：首先看数量的输入，可以判断，奇数位和偶数位的数字肯定不同，所以可以先分别记录奇数位和偶数位的数字个数和sum1 sum2，然后再分别记录0和1数量 num0 num1，并使用两个队列，将所有01按输入的顺序存入，分别计算当sum1==num0,sum2==num1或sum1==num1,sum2==num0时需移动的次数，最后选择输出
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int s[20];
int num[20];
queue<int>q1;
queue<int>q2;
int main()
{
int m,n;
while(~scanf("%d%d",&m,&n))
{
for(int i=0;i<m;i++)
scanf("%d",&s[i]);
int num1=0,num0=0;
int cnt1=0,cnt2=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
if(i%2)
cnt1+=num[i];
else
cnt2+=num[i];
}
if(n==1)
{
printf("0\n");
continue;
}
for(int i=0;i<m;i++)
{
if(s[i]==1)
num1++;
else
num0++;
q1.push(s[i]);
q2.push(s[i]);
}
int tp1=0,tp2=0;
if(num1==num0||num0==cnt1)
{
int num_0=0,num_1=0,ans=1;
while(!q1.empty())
{
if(ans%2==0)//判断是奇数位还是偶数位
{
if(num_1>=num[ans])//1的个数比需要的多
{
num_1-=num[ans];
ans++;
continue;
}
}
else
{
if(num_0>=num[ans])
{
num_0-=num[ans];
ans++;
continue;
}
}
int a=q1.front();
q1.pop();
if(ans%2==0)
{
if(a==1)
{
num_1++;
tp1+=num_0;//有一个1则0需移一位，共移num_0位
if(num_1>=num[ans])
{
num_1-=num[ans];
ans++;
}
}
else
{
num_0++;
}
}
else
{
if(a==0)
{
num_0++;
tp1+=num_1;
if(num_0>=num[ans])
{
num_0-=num[ans];
ans++;
}
}
else
{
num_1++;
}
}
}
}
if(num1==num0||num1==cnt1)
{
int ans=1,num_0=0,num_1=0;
while(!q2.empty())
{
if(ans%2==1)
{
if(num_1>=num[ans])
{
num_1-=num[ans];
ans++;
continue;
}
}
else
{
if(num_0>=num[ans])
{
num_0-=num[ans];
ans++;
continue;
}
}
int a=q2.front();
q2.pop();
if(ans%2==1)
{
if(a==1)
{
num_1++;
tp2+=num_0;
if(num_1>=num[ans])
{
num_1-=num[ans];
ans++;
}
}
else
{
num_0++;
}
}
else
{
if(a==0)
{
num_0++;
tp2+=num_1;
if(num_0>=num[ans])
{
num_0-=num[ans];
ans++;
}
}
else
{
num_1++;
}
}
}
}
if(num1==num0)//01个数相同则取最小
printf("%d\n",min(tp1,tp2));
else//否则要取大的，因为另一个是零
printf("%d\n",max(tp1,tp2));
}
return 0;
}
/**********************************************************************
Problem: 1275
User: multi2018team004
Language: C++
Result: AC
Time:4 ms
Memory:2024 kb
**********************************************************************/
京公网安备 11010502036488号