Problem F: Nostop玩硬币(模拟+贪心)代码笔记本-

https://www.yyycode.cn/index.php/2020/06/13/problem-f-no_stop%e7%8e%a9%e7%a1%ac%e5%b8%81%e6%a8%a1%e6%8b%9f%e8%b4%aa%e5%bf%83/

Description

No_stop特别喜欢玩硬币， 而且是他只喜欢自己一个人玩。第一次玩，他会把一些硬币排成一排，硬币要么是正面朝上(看成是1)要么是反面朝上(看成0)，那么这样会产生一个二进制数(设为数a)，No_stop会把它记录下来。他觉得玩一次不过瘾，所以会玩很多次，以后他每次玩会重新拿一些硬币重新排列，他要求每次硬币正面朝上的个数与上一次保持不变，由于他有很强很强的强迫症，他必须让产生数a越来越大，而且要让两次产生的数的差值尽可能小。现在给你No_stop第一次的硬币排列，问你他第二次玩的硬币排列是多少？

Input

第一行输入一个组数T(T<= 30)，对于每一组测试数据，输入一个“01”序列(1<=长度<= 10)，且 序列的第一个数字不为0。 

Output

对于每组测试数据，输出一个“01”序列。

Sample Input

 1 1010101 

Sample Output

 1010110 

HINT

提示：这个硬币的总长是可以变的。因为题目说重新找一堆硬币。

我们看样例： 1010110

最少的增加方法是1011010

然后是 1011100

然后是 1101100

可以发现：从右边往前面找，找到第一个0并且这个0的右边是1的时候，交换这两个数就是最优的

当这样下去后，会出现1111000这样的情况。

这时候我们要加一位 0,变成 01111000.然后变大

最优的情况是 10000111.

这里可以用等比数列证明：

举个例子,1110,现在变成01110. 唯一变大的法子是把第一个0换成一个1，这时候，二进制的和是2^(n+1);原来的是(2^1+2^2+2^3+….+2^n)求和可判断当第一个0变成1之后，大于前面的数。然后把多余的1全部移到最后就是该情况的最优解

 #include<iostream> #include<vector> #include<queue> #include<cstring> #include<algorithm> using namespace std; const int maxn=1e5; typedef long long LL;  int main(void) {  LL t;  cin>>t;  while(t--)  {    string str;   cin>>str;   int flag=1;   for(LL i=str.size();i>=0;i--)   {    if(str[i]=='1'&&str[i-1]=='0'&&flag==1)    {     swap(str[i],str[i-1]);     cout<<str<<endl;     flag=0;     break;    }   }   if(flag)   {    LL cnt1=0;LL cnt2=0;    for(LL i=0;i<str.size();i++)    {     if(str[i]=='1') cnt1++;    }    cout<<"1";    for(int i=1;i<=str.size()-cnt1+1;i++)      cout<<"0";    for(int i=1;i<=cnt1-1;i++)     cout<<"1";    cout<<endl;      }  }  return 0; }