4122: No_stop玩硬币
Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 268  Solved: 27

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

Source
Jiong King

简单的思路是，把产生的二进制数不断加1，知道与上一个二进制数中的1数量相同，，可以要怎么实现呀~~~？求教

我写的错误代码（只有题目测试数据能对，用1,111,100都不对），新人乱写的，求个正确的代码
#include<stdio.h>
#include<string.h>
int main()
{
    int T,j,i,k,q,n,count,recount,flag,w;
    char b[10],a[10];
    scanf("%d",&T);
    getchar();
    for(j=0;j<T;j++)
    {
        gets(b);
        n=strlen(b);
        q=0;count=0;recount=0;
        memset(a,0,sizeof(a));
        for(i=n-1;i>=0;i--)//zhuan zhi
        {
            if(b[i]=='1')
            {count++;}
            a[q]=b[i];
            q++;
        }
        flag=0;
         while(count!=0)
 {
     i=0;
     while(a[i]>='0')//mei ci jia 1
            {
                a[i]+=1;
                if(i>n-1)
                {
                     for(k=0;k<10;k++)
                    {
                        if(a[k]=='1')
                        {recount++;}
                    }
                    if(recount==count)
                    {flag=1;}
                    break;
                }
                if(a[i]>'1')
                {
                    a[i]='0';
                    i++;
                }
                else
                {
                    for(k=0;k<10;k++)//tong ji bu fen
                    {
                        if(a[k]=='1')
                        {recount++;}
                    }
                    if(recount==count)
                    {flag=1;break;}
                }
            }
            if(flag==1)
            {break;}
}
        q=0;
        for(i=9;i>=0;i--)//zhuan zhi
        {
            b[q]=a[i];
            q++;
        }
        for(i=0;i<10;i++)//zhao dao di yi ge '1'
        {
            if(b[i]=='1')
            {w=i;
             break;}
        }
        for(i=w;i<10;i++)//shu chu
        {
            printf("%c",b[i]);
        }
        printf("\n");
    }
    return 0;
}
      

我来教你一个排序组合的算法吧，也就是std::next_permutation算法的简化：

先读入“01”序列，并在最前面补上一个0，得到 0abcdefghij
从后向前遍历，找到第一个1的位置i，并把a[i]设为0
从i-1向前遍历，找到第一个0的位置j，并把a[j]设为1
将j之后的序列反序一下


[ 本帖最后由 rjsp 于 2013-12-18 10:55 编辑 ]

最好求算法，自己实现，

供参考，我也不知道对不对

#include <stdio.h>
#include <string.h>

int main()
{
    unsigned t;
    scanf( "%u", &t );
    for( ; t; --t )
    {
        char a[12] = "0"; // 首部补一个'0'是为了确保不需要增加位数
        scanf( "%s", a+1 );

        size_t n = strlen(a);

        // 从后向前遍历，找到第一个1的位置i，并把a[i]设为0
        size_t i = n-1;
        for( ; a[i]=='0'; --i );
        a[i] = '0';

        // 从i-1向前遍历，找到第一个0的位置j，并把a[j]设为1
        size_t j = i-1;
        for( ; a[j]=='1'; --j );
        a[j] = '1';

        // 将j之后的序列反序一下
        for( size_t k=j+1; k<n-k+j; ++k )
        {
            char tmp = a[k];
            a[k] = a[n-k+j];
            a[n-k+j] = tmp;
        }

        printf( "%s\n", a[0]=='0' ? a+1 : a );
    }

    return 0;
}

找到串中最后一个 ‘01’序列，替换为‘10’即可，如果找不到，说明已经是最大（X）

想当然了，楼上的逆序也不对，应该是移动，把 j之后所有的 ‘1’移到最后

[ 本帖最后由 azzbcc 于 2013-12-18 14:37 编辑 ]

j之后一定是 1……1 0……0 这种形式
1…(a个1)…1 0…(b个0)…0 变为 0…(b个0)…0 1…(a个1)…1 就是逆序
当然，你也可以将之看成是将1移动到最后（即“排序”）。

标准排列组合算法中，使用“逆序”，而不是“排序”，因为j之后的序列一定是从大到小有序的，“逆序”就如同“排序”，并且执行效率更高。

观摩。。。

向 R 版学习，此题考虑不周全。