文章目錄

• • 1. 題目
  • • 1.1 題目鏈接
    • 1.2 題目大意
    • 1.3 解題思路
  • 2. Accepted 代碼

1. 題目

1.1 題目鏈接

http://poj.org/problem?id=2453

1.2 題目大意

一個(gè)數(shù)x的二進(jìn)制表示有n個(gè)1，求一個(gè)有相同個(gè)數(shù)1的二進(jìn)制數(shù)（比x大，且要最小的）

1.3 解題思路

• 求出該數(shù)的二進(jìn)制表示
• 從低位往高位找到第一個(gè)為1的位 i ，檢查其下一位 i+1
• i+1 位值為 0，直接交換01，結(jié)束查找
• i+1 位值為1，將 i 位的1不斷地與前面的交換，換至最低位
• 重復(fù)以上過程

2. Accepted 代碼

/*** @description: 貪心應(yīng)用poj2453* @author: michael ming* @date: 2019/7/2 20:46* @modified by:*/ #include <cstring> #include <iostream> using namespace std;int calc(int num, int *binarynum) {int i = 0, j, k, value = 0;while(num != 0){binarynum[i++] = num % 2;//數(shù)組存儲(chǔ)的是該數(shù)的二進(jìn)制的反序序列num = num/2;}k = i;//k記錄最后一個(gè)有效位的下一位for(i = 0; i < k; ++i){if(binarynum[i] == 0)continue;//找到為1的iif(binarynum[i+1] == 0)//如果i的下一個(gè)為0{swap(binarynum[i],binarynum[i+1]);//交換完成尋找break;}for(j = i; j >= 1; --j)//否則將i處的1換到最開始{swap(binarynum[j],binarynum[j-1]);}}for(i = k; i >= 0; --i)//計(jì)算對(duì)應(yīng)的10進(jìn)制數(shù)值//最后一位k-1可能進(jìn)位到k，所以i從k開始value = value*2 + binarynum[i];return value; } int main() {int binarynum[30];//數(shù)據(jù)大小不會(huì)超過30位2進(jìn)制int num;while(cin >> num && num){memset(binarynum,0,30*sizeof(int));cout << calc(num,binarynum) << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ 2453 贪心应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。