《算法竞赛·快冲300题》每日一题：“特殊数字”

《算法竞赛·快冲300题》将于2024年出版，是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码，以中低档题为主，适合入门、进阶。

“ 特殊数字” ，链接： http://oj.ecustacm.cn/problem.php?id=1817

题目描述

【题目描述】 N=2^x+2y，并且x≠y，则称N为特殊数字。
   现在给定数字x，每次可以进行两种操作：令x加1、令x减1。
   最少执行多少次操作，可以将x变成特殊数字。
【输入格式】 第一行为正整数T，表示存在T组测试数据，1≤T≤10000。
   每组数据输入一行，包含一个整数x，1≤x≤10^9。
**【输出格式】**每组数据输出一行表示答案。
【输入样例】

3
10
22
4

【输出样例】

0
2
1

---

题解

   由于直接对x进行加1减1的操作然后判断是否为特殊数字十分耗时，这不是好办法。容易想到的简单的办法是提前算出所有的特殊数字，然后找与x最近的数字。
   有多少特殊数字，计算量大吗？题目给定$x\le 10^9$，而$10^9<2^{30}$，对于$N=2^x+2^y$，只需分别把$2^x、2^y$计算算到$2^{30}$，一共30×30次就够了。
   接下来是找距离x最近的数字。先把特殊数字排序，然后用二分法找距离x最近的数即可。
【重点】 二分法、lower_bound() 。

C++代码

   STL有一个二分法函数lower_bound()（lower_bound()的用法见《算法竞赛》，清华大学出版社，罗勇军、郭卫斌著，46页），它的功能是在有序序列中找x或附近的数，正符合本题的要求。

#include<bits/stdc++.h>
using namespace std;
int a[910], tot;
int main(){for(int i = 0; i <= 30; i++)          //预先处理出所有特殊数字for(int j = i + 1; j <= 30; j++)  //i和j不同a[tot++] = (1 << i) + (1 << j);sort(a, a + tot);                     //二分之前先排序int T;   cin >> T;while(T--) {int x; cin >> x;int p = lower_bound(a, a + tot, x) - a;  //查找第一个大于等于x的位置p，即a[p]>=xint ans = 0;if(a[p] == x)  ans = 0;else {ans = a[p] - x;                      //a[p]比x大if(p - 1 > 0)                        ans = min(ans, x - a[p - 1]);    //比x大和比x小的最近2个数}cout<<ans<<endl;}return 0;
}

   作为对照，下面给出手写二分法的代码。

#include<bits/stdc++.h>
using namespace std;
int a[910],tot;
int main(){for (int i = 0;i <= 30;i++)for (int j = i + 1;j <= 30;j++)a[tot++] = (1 << i) + (1 << j);sort(a , a + tot);int T; cin >> T;while (T--)  {int x; cin >> x;int L = 0 , R = tot;while (L < R)     {int mid = L + R >> 1;if (a[mid] >= x)   R = mid;else L = mid + 1;}int ans;if (a[L] == x)  ans = 0;else  {ans = a[L] - x;if (L > 0) ans = min(ans , x - a[L - 1]);}cout << ans << endl;}return 0;
}

Java代码

   Java也有和C++的lower_bound()类似的函数binarySearch()。注意binarySearch()的返回值，如果找不到x，它的返回值是负的。

 import java.util.*;
public class Main {public static void main(String[] args) {int[] a = new int[910];int tot = 0;for(int i = 0; i <= 30; i++)             //预先处理出所有特殊数字for(int j = i + 1; j <= 30; j++)     //i和j不同a[tot++] = (1 << i) + (1 << j);        Arrays.sort(a, 0, tot);                  //二分之前先排序Scanner sc = new Scanner(System.in);int T = sc.nextInt();while(T-- > 0) {int x = sc.nextInt();int p = Arrays.binarySearch(a, 0, tot, x);if(p < 0) {                       //a[]中没有x，返回的p是负的p = -p - 1;int ans = a[p] - x;           //a[p]比x大if(p - 1 >= 0)ans = Math.min(ans, x - a[p - 1]);   //比x大和比x小的最近2个数System.out.println(ans);}else {                           //a[]中有x，返回的p是数组下标 System.out.println(0);}}sc.close();}
}

   作为对照，下面给出手写二分法的Java代码。

 import java.util.Arrays;
import java.util.Scanner;
public class Main {public static void main(String[] args) {int[] a = new int[910];int tot = 0;for (int i = 0; i <= 30; i++)for (int j = i + 1; j <= 30; j++)a[tot++] = (1 << i) + (1 << j);Arrays.sort(a, 0, tot);Scanner sc = new Scanner(System.in);int T = sc.nextInt();while (T-- > 0) {int x = sc.nextInt();int L = 0, R = tot;while (L < R) {int mid = (L + R) >> 1;if (a[mid] >= x)   R = mid;else               L = mid + 1;}int ans;if (a[L] == x)  ans = 0;else {ans = a[L] - x;if (L > 0)  ans = Math.min(ans, x - a[L - 1]);}System.out.println(ans);}}
}

Python代码

   Python也有和C++的lower_bound()类似的函数bisect_left()。

import bisect
a = []
for i in range(31):for j in range(i+1,31):a.append((1 << i) + (1 << j))    
a.sort()
t = int(input())
for _ in range(t):x = int(input())p = bisect.bisect_left(a,x)print(min(abs(a[p]-x),abs(a[p-1]-x)))

   作为对照，下面给出手写二分法的Python代码。

a = []
for i in range(31):for j in range(i+1, 31):a.append((1 << i) + (1 << j)) 
a.sort()
T = int(input())
for _ in range(T):x = int(input())L, R = 0, len(a)while L < R:mid = (L + R) // 2if a[mid] >= x:  R = midelse:            L = mid + 1if a[L] == x:  ans = 0else:ans = a[L] - xif L > 0:  ans = min(ans, x - a[L-1])print(ans)