公司企业网站建设步骤,执行信息公开网,怎么设自己的网站,国家重大建设项目库填报网站1 题目描述
查找成绩10开启时间2021年09月24日 星期五 18:00折扣0.8折扣时间2021年11月15日 星期一 00:00允许迟交否关闭时间2021年11月23日 星期二 00:00 输入 n(n ≤ 10^6)个不超过 10^9的单调不减的#xff08;就是后面的数字不小于前面的数字#xff09;非负整数 #…1 题目描述
查找
成绩10开启时间2021年09月24日 星期五 18:00折扣0.8折扣时间2021年11月15日 星期一 00:00允许迟交否关闭时间2021年11月23日 星期二 00:00 输入 n(n ≤ 10^6)个不超过 10^9的单调不减的就是后面的数字不小于前面的数字非负整数 然后进行 m(m ≤ 10^5) 次询问。对于每次询问给出一个整数 q(q ≤ 10^9)要求输出这个数字在序列中第一次出现的编号如果没有找到的话输出 -1 。输入描述第一行 2 个整数 n 和 m表示数字个数和询问次数。第二行 n 个整数表示这些待查询的数字有序第三行 m 个整数表示询问这些数字的编号从 1 开始编号。输出描述m 个整数表示答案注意换行。接下来将由系统输出你的询问记录。当你的答案正确且你询问的次数在( 2 * m * log(n) ) 3次以内时你将AC此题。此题log以2为底。PS部分超过时间限制的可多次提交即可通过预设代码前置代码 /* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */ #include bits/stdc.h int n, m, q, a[1000005]; int find(int x,int n);
int cmp(int i, int x)
{ if(i n|| i 0) return -2; if (a[i] x) return 1; if (a[i] x) return 0; return -1;
} int main()
{ scanf(%d %d, n, m); //读入 for (int i 1; i n; i) scanf(%d, a[i]); //还是读入 for (int i 1; i m; i) { scanf(%d, q); int ans find(q,n); //看看查找的结果 printf(%d , ans); //输出 } printf(\n); return 0;
} // //请补充下列代码
// int find(int x,int n)
// { // } /* PRESET CODE END - NEVER TOUCH CODE ABOVE */ 测试输入 期待的输出 时间限制 内存限制 额外进程 测试用例 1以文本方式显示11 3↵1 3 3 3 5 7 9 11 13 15 15↵1 3 6↵以文本方式显示1 2 -1 ↵1秒153600KB0 2 代码
#include bits/stdc.h int n, m, q, a[1000005]; int find(int x,int n);
int cmp(int i, int x)
{ if(i n|| i 0) return -2; if (a[i] x) return 1; if (a[i] x) return 0; return -1;
} int main()
{ freopen(file in.txt,r,stdin);scanf(%d %d, n, m); //读入 for (int i 1; i n; i) scanf(%d, a[i]); //还是读入 for (int i 1; i m; i) { scanf(%d, q); int ans find(q,n); //看看查找的结果 printf(%d , ans); //输出 } printf(\n); return 0;
} // //请补充下列代码
//找x在a中第一次出现的编号
// int find(int x,int n)
// {
// int mid;
// int ans;
// int left,right;
// int flag0;// left1;rightn;
// mid0;// //数字个数大于等于3个才会进入这个循环
// while(leftright-1){// /*if((right-left1)%21){
// // 奇数
// mid (right-left)/2left;
// }
// else{
// mid (right-left)/2left;
// }*/
// //不用考虑奇偶性
// mid (right-left)/2left;
// // 比较中间这个数和x的大小
// ans cmp(mid,x);
// if(ans-2){
// exit;
// }
// else if(ans1){
// // 这个数在左边
// right mid;
// }
// else if(ans-1){
// //这个数在右边
// leftmid;
// }
// else{
// // 找到了
// flag1;
// break;
// }
// }
// //如果上面的循环没有找到,那么还剩下三个数没有找 left left1 right
// // 或者说直接没有进入上面的while循环中
// if(flag0){
// while(leftright){
// ans cmp(left,x);
// if(ans0){
// //找到的话直接返回left的值并且退出这个函数了
// return left;
// }
// else{
// left; // }
// }
// //如果循环走完了都没有退出这个函数说明没有找到相等的数
// return -1;
// }// //如果是在while循环里面找到的就会运行下面的语句
// if(flag){
// //找到了这个数但是还要验证他是不是第一次出现
// while(mid-11){
// anscmp(mid-1,x);
// if(ans0){
// //他的前一个数还是和他相等
// mid--;
// }
// else{
// //他的前一个数和x不相等那么现在这个mid就是我们要找的第一次出现的x
// break;
// }
// }
// return mid;
// }
// else
// return -1;
// }// 再循环里面找到这个数的时候不要退出继续循环二分法
// 如果前面有的话最终会落在这个数上面如果没有的话最后left也会回到这个数和right相等
int find(int x, int n){int left,right;int mid;int ans;int flag0,temp;left1;rightn;while(leftright){// 没有必要区分奇偶这里只需要让mid取中就行并不是前面那种两个两个拿出来会有一个落单的情况mid(right-left)/2left;ans cmp(mid,x);if(ans-2){exit(0);}else if(ans1){// mid这个数已经比较过了不用在比较了直接向前面推进一个数right mid-1;}else if(ans-1){leftmid1;}else{right mid-1;//不往前推的话这个就会进入死循环tempmid;//把这个数记录下来防止往前推以后没有这个数了flag1;}}// 循环结束之后if(ans0)return left;else if(flag1)return temp;return -1;
}// 不用区分n的奇偶性
// mid比较过后应该跳过简化了算法的复杂度
