hihocoder第三十六周 二分查找
2024-09-06 20:37:14
题目链接:http://hihocoder.com/contest/hiho36/problem/1 , 一个比较简单的二分。
算法:
由于数据量比较大,O(nlogn)无法通过,所以不能先排序再查找。由于题目中问的是在排序后的位置,所以可以想到快速排序中一趟排序后,作为支点的那个值的坐标就已经确定下来了,所以可以把要查找的k作为支点,这样的话一趟排序后(即把比k小的放在k之前,比k大的放在k之后),k的坐标即为所求。
至于给的提示表示没看懂。。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = + ;
int a[maxn];
int main()
{
int n , k , i , j , pos;
scanf("%d %d" , &n , &k);
for(i = ; i <= n ; i++) {
scanf("%d" , &a[i]);
}
for(pos = ; pos <= n ; pos++)
if(a[pos] == k)
break;
if(pos > n) {
printf("-1\n");
} else {
i = ;
j = n;
while(i != j) {
while(a[j] > k && j > pos)
j--;
a[pos] = a[j];
pos = j;
while(a[i] < k && i < pos)
i++;
a[pos] = a[i];
pos = i;
}
printf("%d\n" , i);
}
return ;
}
最新文章
- Windows 搭建jdk、Tomcat、eclipse以及SVN、maven插件开发环境
- XCode6.3上使用opencv教程(MacOSX 10.10)
- Orchard搜索与索引
- go 的 protoc 插件调用逻辑
- hadoop学习记录(四)hadoop2.6 hive配置
- [scalability] Find all documents that contain a list of words
- pywinauto简单介绍
- JS JQuery Ajax 跨域 Post Soap webservice
- Oracle Dataguard三种保护模式
- java异常详解
- C++ 获取文件夹下的所有文件名
- MySQL迁移方案(后续再补充)
- Flume环境搭建_五种案例
- [蓝桥杯]PREV-25.历届试题_城市建设
- 秒懂AOP
- FZU软工第五次作业-词组频率分析
- Thrift源码学习二——Server层
- led灯的驱动电流和电阻
- Jungle Roads_hdu_1301(prim算法)
- security权限控制