网站后端技术有哪些,网站后台主流网站开发语言,新闻发布会策划流程,网页设计立项书怎么写《算法竞赛快冲300题》将于2024年出版#xff0c;是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码#xff0c;以中低档题为主#xff0c;适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
特…《算法竞赛·快冲300题》将于2024年出版是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码以中低档题为主适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
特殊数字” 链接
http://oj.ecustacm.cn/problem.php?id1817 题目描述
【题目描述】 N2x2y并且x≠y则称N为特殊数字。 现在给定数字x每次可以进行两种操作令x加1、令x减1。 最少执行多少次操作可以将x变成特殊数字。 【输入格式】 第一行为正整数T表示存在T组测试数据1≤T≤10000。 每组数据输入一行包含一个整数x1≤x≤10^9。 **【输出格式】**每组数据输出一行表示答案。 【输入样例】
3
10
22
4【输出样例】
0
2
1题解 由于直接对x进行加1减1的操作然后判断是否为特殊数字十分耗时这不是好办法。容易想到的简单的办法是提前算出所有的特殊数字然后找与x最近的数字。 有多少特殊数字计算量大吗题目给定 x ≤ 1 0 9 x≤10^9 x≤109而 1 0 9 2 30 10^9 2^{30} 109230对于 N 2 x 2 y N 2^x 2^y N2x2y只需分别把 2 x 、 2 y 2^x、2^y 2x、2y计算算到 2 30 2^{30} 230一共30×30次就够了。 接下来是找距离x最近的数字。先把特殊数字排序然后用二分法找距离x最近的数即可。 【重点】 二分法、lower_bound() 。
C代码 STL有一个二分法函数lower_bound()lower_bound()的用法见《算法竞赛》清华大学出版社罗勇军、郭卫斌著46页它的功能是在有序序列中找x或附近的数正符合本题的要求。
#includebits/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个数}coutansendl;}return 0;
}作为对照下面给出手写二分法的代码。
#includebits/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(i1,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(i1, 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)
