LightOJ 1042 Secret Origins（贪心）

心已赠人 2022-06-09 06:20 151阅读 0赞

This is the tale of Zephyr, the greatest time traveler the world will never know. Even those who are aware of Zephyr's existence know very little about her. For example, no one has any clue as to which time period she is originally from.

But we do know the story of the first time she set out to chart her own path in the time stream. Zephyr had just finished building her time machine which she named - "Dokhina Batash". She was making the final adjustments for her first trip when she noticed that a vital program was not working correctly. The program was supposed to take a number **N**, and find what Zephyr called its Onoroy value.

The Onoroy value of an integer **N** is the number of ones in its binary representation. For example, the number 13 (11012) has an Onoroy value of 3. Needless to say, this was an easy problem for the great mind of Zephyr. She solved it quickly, and was on her way.

You are now given a similar task. Find the first number after **N** which has the same Onoroy value as **N**.

Input

Input starts with an integer **T (≤ 65)**, denoting the number of test cases.

Each case begins with an integer **N (1 ≤ N ≤ 109)**.

Output

For each case of input you have to print the case number and the desired result.

Sample Input

14232

391

Sample Output

Case 1: 27

Case 2: 14241

Case 3: 395

Case 4: 11

Case 5: 16

题解：

题意：

给你一个数，让你转化成2进制以后，要求求一个比该数大的第一个数而且这个数二进制表示时1的个数要和原数相同（可以最后面加0）

思路：

先将数字转化成二进制，找到最后一个01改成10，再把这个段后面的1全部放到后面就行了，如果找不到就在最后面加一个0，把除第一位以外的1都放最后面就行了

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define ll long long
    #define eps 1e-15
    int a[105];
    int cmp(int x,int y)
    {
        return x>y;
    }
    int main()
    {
        int i,j,test,q,len;
        scanf("%d",&test);
        ll x,y;
        for(q=1;q<=test;q++)
        {
            scanf("%lld",&x);
            memset(a,0,sizeof(a));
            len=0;
            while(x>0)
            {
                a[len]=x%2;
                x/=2;
                len++;
            }
            int tag=0;
            for(i=0;i<len-1;i++)
            {
                if(a[i]==1&&a[i+1]==0)
                {
                    tag=1;
                    swap(a[i],a[i+1]);
                    sort(a,a+i,cmp);
                    break;
                }
            }
            if(!tag)
            {
                for(i=len;i>=1;i--)
                {
                    a[i]=a[i-1];
                }
                a[0]=0;
                sort(a,a+len,cmp);
                len++;
            }
            ll sum=0;
            x=1;
            for(i=0;i<len;i++)
            {
                sum=sum+a[i]*x;
                x=x*2;
            }
            printf("Case %d: %lld\n",q,sum);
        }
        return 0;
    }