【南理oj】412 - Same binary weight（STL - 双端队列 & 全排列）

点击打开题目

Same binary weight

时间限制： 300 ms | 内存限制： 65535 KB

难度： 3

描述

The binary weight of a positive integer is the number of 1's in its binary representation.for example,the decmial number 1 has a binary weight of 1,and the decimal number 1717 (which is 11010110101 in binary) has a binary weight of 7.Give a positive integer N,return the smallest integer greater than N that has the same binary weight as N.N will be between 1 and 1000000000,inclusive,the result is guaranteed to fit in a signed 32-bit interget.

输入 The input has multicases and each case contains a integer N. 输出 For each case,output the smallest integer greater than N that has the same binary weight as N. 样例输入

1717
4
7
12
555555

样例输出

1718
8
11
17
555557

来源 topcoder 上传者 骆魁永

用双端队列加全排列省时省力。

把其二进制列好后，在最前面加一个前导0，然后生成下一个全排列，然后转换为十进制输出即可。

代码如下：

#include <cstdio>
#include <deque>
#include <algorithm>
using namespace std;
int main()
{
	int n;
	int num;
	int ans;
	while (~scanf ("%d",&n))
	{
		deque<int> q;
		while (n)		//将数字的二进制存入双端队列 
		{
			q.push_front(n & 1);
			n >>= 1;
		}
		q.push_front(0);
		next_permutation(q.begin(),q.end());
		ans = 0;
		num = 0;
		while (!q.empty())
		{
			ans += (q.back() << num);
			num++;
			q.pop_back();
		}
		printf ("%d\n",ans);
	}
	return 0;
}