#1128 : 二分·二分查找 ( 两种方法 先排序在二分O(nlogN) + 直接二分+快排思想O(2N) )

2024-08-30 21:08

本文主要是介绍#1128 : 二分·二分查找 ( 两种方法 先排序在二分O(nlogN) + 直接二分+快排思想O(2N) ),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


#1128 : 二分·二分查找
时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

Nettle最近在玩《艦これ》,因此Nettle收集了很多很多的船(这里我们假设Nettle氪了很多金,开了无数个船位)。去除掉重复的船之后,还剩下N(1≤N≤1,000,000)种不同的船。每一艘船有一个稀有值,任意两艘船的稀有值都不相同,稀有值越小的船越稀有,价值也就越高。
Nettle现在通过大建又造出了一艘船,他想知道这艘船是不是重复的。如果是重复的,那么这艘船在Nettle所有的船里面稀有值排多少位。

问题一
Nettle已经先把自己所有船按照稀有值从小到大排列好了(a[1..N]),我们要做的是看看新得到的船(假设稀有值为K)是否在这个序列中,且有对应的a[i]=K时,i为多少?

提示一:有序数组的二分查找
问题二
因为Nettle的船太多了,他不愿意去给所有船按照稀有值排序,而是直接告诉了我们每一艘船的稀有值。在这种情况下我们该如何解决这个问题呢?

提示二:非有序数组的二分查找
输入

第1行:2个整数N,K。N表示数组长度,K表示需要查找的数;
第2行:N个整数,表示a[1..N],保证不会出现重复的数,1≤a[i]≤2,000,000,000。
输出

第1行:一个整数t,表示K在数组中是第t小的数,若K不在数组中,输出-1。
样例输入

10 5180
2970 663 5480 4192 4949 1 1387 4428 5180 2761

样例输出

9

//先排序在二分  48ms

#include<cstdio>
#include<algorithm>
//#include<bits/stdc++.h>
using namespace std;
template<class T>inline T read(T&x)
{char c;while((c=getchar())<=32)if(c==EOF)return 0;bool ok=false;if(c=='-')ok=true,c=getchar();for(x=0; c>32; c=getchar())x=x*10+c-'0';if(ok)x=-x;return 1;
}
template<class T> inline T read_(T&x,T&y)
{return read(x)&&read(y);
}
template<class T> inline T read__(T&x,T&y,T&z)
{return read(x)&&read(y)&&read(z);
}
template<class T> inline void write(T x)
{if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else write(x/10),putchar(x%10+'0');
}
template<class T>inline void writeln(T x)
{write(x);putchar('\n');
}
//-------ZCC IO template------
const int maxn=1000011;
const double inf=999999999;
#define lson (rt<<1),L,M
#define rson (rt<<1|1),M+1,R
#define M ((L+R)>>1)
#define For(i,t,n) for(int i=(t);i<(n);i++)
typedef long long  LL;
typedef double DB;
typedef pair<int,int> P;
#define bug printf("---\n");
#define mod 10007LL a[maxn];
int bs(int left,int right,int key)
{while(left<=right){int mid=(left+right)>>1;if(key==a[mid])return mid;else if(a[mid]>key)right=mid-1;elseleft=mid+1;}return -1;
}int main()
{//#ifndef ONLINE_JUDGE// freopen("in.txt","r",stdin);//#endif // ONLINE_JUDGEint n,m,i,j,k,t;while(read_(n,k)){For(i,1,n+1){read(a[i]);}sort(a+1,a+n+1);writeln(bs(1,n+1,k));}return 0;
}


//用二分的思想, 28ms#include<cstdio>
#include<algorithm>
//#include<bits/stdc++.h>
using namespace std;
template<class T>inline T read(T&x)
{char c;while((c=getchar())<=32)if(c==EOF)return 0;bool ok=false;if(c=='-')ok=true,c=getchar();for(x=0; c>32; c=getchar())x=x*10+c-'0';if(ok)x=-x;return 1;
}
template<class T> inline T read_(T&x,T&y)
{return read(x)&&read(y);
}
template<class T> inline T read__(T&x,T&y,T&z)
{return read(x)&&read(y)&&read(z);
}
template<class T> inline void write(T x)
{if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else write(x/10),putchar(x%10+'0');
}
template<class T>inline void writeln(T x)
{write(x);putchar('\n');
}
//-------ZCC IO template------
const int maxn=1000011;
const double inf=999999999;
#define lson (rt<<1),L,M
#define rson (rt<<1|1),M+1,R
#define M ((L+R)>>1)
#define For(i,t,n) for(int i=(t);i<(n);i++)
typedef long long  LL;
typedef double DB;
typedef pair<int,int> P;
#define bug printf("---\n");
#define mod 10007
LL a[maxn];
int bs(int left,int right,int key)
{if(left>right){if(a[left]==key)return left-1;else return -1;}int mid=a[left];int low=left;int high=right;while(low<high)
{
while(low<high&&a[high]>=mid)
high--;
if(low<high)swap(a[high],a[low]);
while(low<high&&a[low]<=mid)
low++;
if(low<high)swap(a[high],a[low]);
}if(mid<key)return bs(low+1,right,key);elsereturn bs(left,low-1,key);
}int main()
{//#ifndef ONLINE_JUDGE// freopen("in.txt","r",stdin);//#endif // ONLINE_JUDGEint n,m,i,j,k,t;while(read_(n,k)){For(i,1,n+1){read(a[i]);}writeln(bs(1,n+1,k));}return 0;
}



这篇关于#1128 : 二分·二分查找 ( 两种方法 先排序在二分O(nlogN) + 直接二分+快排思想O(2N) )的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1121934

相关文章

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

webm怎么转换成mp4?这几种方法超多人在用!

webm怎么转换成mp4?WebM作为一种新兴的视频编码格式,近年来逐渐进入大众视野,其背后承载着诸多优势,但同时也伴随着不容忽视的局限性,首要挑战在于其兼容性边界,尽管WebM已广泛适应于众多网站与软件平台,但在特定应用环境或老旧设备上,其兼容难题依旧凸显,为用户体验带来不便,再者,WebM格式的非普适性也体现在编辑流程上,由于它并非行业内的通用标准,编辑过程中可能会遭遇格式不兼容的障碍,导致操

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时