题目链接: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 ;
}

最新文章

  1. Windows 搭建jdk、Tomcat、eclipse以及SVN、maven插件开发环境
  2. XCode6.3上使用opencv教程(MacOSX 10.10)
  3. Orchard搜索与索引
  4. go 的 protoc 插件调用逻辑
  5. hadoop学习记录(四)hadoop2.6 hive配置
  6. [scalability] Find all documents that contain a list of words
  7. pywinauto简单介绍
  8. JS JQuery Ajax 跨域 Post Soap webservice
  9. Oracle Dataguard三种保护模式
  10. java异常详解
  11. C++ 获取文件夹下的所有文件名
  12. MySQL迁移方案(后续再补充)
  13. Flume环境搭建_五种案例
  14. [蓝桥杯]PREV-25.历届试题_城市建设
  15. 秒懂AOP
  16. FZU软工第五次作业-词组频率分析
  17. Thrift源码学习二——Server层
  18. led灯的驱动电流和电阻
  19. Jungle Roads_hdu_1301(prim算法)
  20. security权限控制

热门文章

  1. uWSGI + Nginx + Django 部署
  2. XLua 基础
  3. 《OD学storm》20160828
  4. CTS/APIO2019游记
  5. EOS 多主机多节点配置终极命令
  6. Java基础笔记(十一)—— 字符串与数组
  7. 5、kvm快照相关操作
  8. Helvetic Coding Contest 2016 online mirror C2
  9. Gym 100886J Sockets 二分答案 + 贪心
  10. 海量日志收集利器&#160;——&#160;Flume