php网站开发难吗,临沂网站建设网站推广,做家装的网站有什么不同,海口网站建设fwlit题目描述
小朋友出操#xff0c;按学号从小到大排成一列#xff1b;小明来迟了#xff0c;请你给小明出个主意#xff0c;让他尽快找到他应该排的位置。
算法复杂度要求不高于 nLog(n)#xff1b;学号为整数类型#xff0c;队列规模10000#xff1b;
输入描述
1…题目描述
小朋友出操按学号从小到大排成一列小明来迟了请你给小明出个主意让他尽快找到他应该排的位置。
算法复杂度要求不高于 nLog(n)学号为整数类型队列规模10000
输入描述
1、第一行输入已排成队列的小朋友的学号正整数以”,”隔开 例如93,95,97,100,102,123,155 2、第二行小明学号如 110
输出描述
输出一个数字代表队列位置从 1 开始。
例如
6示例一
输入
93,95,97,100,102,123,155
110输出
6OD 统一题解 将已排好序的学号列表转换成整数列表然后使用二分查找找到小明应该插入的位置 代码
无注释
#include stdio.h
#include stdlib.h
#include string.h
#define MAX_LEN 10001
int find(int id[], int count, int num) {int left 0, right count - 1;while (left right) {int mid (left right) / 2;if (id[mid] num) {left mid 1;} else if (id[mid] num) {right mid - 1;} else {return mid;}}return left;
}
int main() {char input[MAX_LEN];fgets(input, MAX_LEN, stdin);input[strcspn(input, \n)] \0;int id[MAX_LEN];int count 0;char *token strtok(input, ,);while (token ! NULL) {id[count] atoi(token);token strtok(NULL, ,);}int num;scanf(%d, num);int res find(id, count, num);printf(%d\n, res 1);return 0;
}有注释
// 小明找位置问题的解决方案通过二分查找算法实现
#include stdio.h
#include stdlib.h
#include string.h
#define MAX_LEN 10001// 定义二分查找函数输入参数整数数组id、数组长度count以及需要查找的学号num
int find(int id[], int count, int num) {// 初始化二分查找的左右边界int left 0, right count - 1;// 当左边界小于等于右边界时继续循环while (left right) {// 计算中间位置的索引int mid (left right) / 2;// 检查中间位置的学号与目标学号的关系if (id[mid] num) { // 如果中间位置的学号小于目标学号left mid 1; // 移动左边界到中间位置右侧} else if (id[mid] num) { // 如果中间位置的学号大于目标学号right mid - 1; // 移动右边界到中间位置左侧} else { // 如果找到目标学号则返回该位置的索引return mid;}}// 若未找到目标学号返回小明应插入的位置即左边界1return left;
}int main() {// 读取已排序学号字符串char input[MAX_LEN];fgets(input, MAX_LEN, stdin);input[strcspn(input, \n)] \0; // 去掉末尾换行符// 存储转换为整数的学号数组int id[MAX_LEN];int count 0;// 使用strtok函数按逗号分割输入字符串并将每个学号转换为整数存入数组char *token strtok(input, ,);while (token ! NULL) {id[count] atoi(token); // 将字符串学号转换为整数并存储token strtok(NULL, ,); // 继续处理下一个学号}// 读取小明的学号int num;scanf(%d, num);// 调用二分查找函数找出小明应在队列中的位置int res find(id, count, num);// 输出结果由于队列位置从1开始计数所以输出时1printf(%d\n, res 1);return 0;
}
