个人网站名称怎么写,请小组讨论一个完整的网页设计流程,竞价托管外包,微信网站是多少钱Description
给出一个队列和要查找的数值#xff0c;找出数值在队列中的位置#xff0c;队列位置从1开始
要求使用顺序索引查找算法#xff0c;其中索引表查找和块内查找都采用不带哨兵、从头开始的顺序查找方法。
Input
第一行输入n#xff0c;表示主表有n个数据
第二…Description
给出一个队列和要查找的数值找出数值在队列中的位置队列位置从1开始
要求使用顺序索引查找算法其中索引表查找和块内查找都采用不带哨兵、从头开始的顺序查找方法。
Input
第一行输入n表示主表有n个数据
第二行输入n个数据都是正整数用空格隔开
第三行输入k表示主表划分为k个块k也是索引表的长度
第四行输入k个数据表示索引表中每个块的最大值
第五行输入t表示有t个要查找的数值
第六行起输入t个数值输入t行
Output
每行输出一个要查找的数值在队列的位置和查找次数数据之间用短划线隔开如果查找不成功输出字符串error
Sample
#0
Input
18
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53
3
22 48 86
6
13
5
48
40
53
90Output
3-4
error
12-8
error
18-9
error解题思路
一开始忘记了n可能无法整除k导致在构建每个块的时候出错一直卡了很久
AC代码
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N 10010;
int arr[N];
int n, k;struct indexBlock
{int start;int end;int max;
}indexBlocks[N];int blockSearch(int key, int cnt)
{int i 1, j;while (i k cnt key indexBlocks[i].max) { i; }//确认key所在的是哪个子表if (i k)return 0;//i超出了子表的个数找不到keyj indexBlocks[i].start;//j为key所在子表起始下标while (j indexBlocks[i].end cnt arr[j] ! key) { j; }//在确定的块内寻找keyif (j indexBlocks[i].end)return 0;//j超出了所在块范围没有找到keyreturn j;
}int main()
{while (cin n){for (int i 1; i n; i){cin arr[i];}int j 0;cin k;for (int i 1; i k; i){int max;cin max;indexBlocks[i].start j 1;//块的起始下标j j 1;// 找到第一个大于max的数此时j-1就是块的结束下标while (j n){j;if (arr[j] max){j--;break;}}indexBlocks[i].end j;indexBlocks[i].max max;}int t;cin t;while (t--){int key, cnt 0;cin key;int index blockSearch(key, cnt);if (index)cout index - cnt endl;else cout error endl;}}return 0;
}
