文档章节

Tyvj 第K极数

Anemax
 Anemax
发布于 2017/06/18 21:31
字数 196
阅读 1
收藏 0

求第K极数用了二分法 , 剩下的没什么好说。

#include <stdio.h>
#include <math.h>

int MinK(int A[],int n,int k)  
{  
    int s=-1,i=0,j=n-1,temp;  
    int beg=i;  
    int end=j;  
    while(s!=k)  
    {  
        beg=i;  
        end=j;  
        temp=A[i];  
        while(i<j)  
        {  
            while(i<j&&A[j]>=temp)
                j--;
            A[i]=A[j];  
            while(i<j&&A[i]<=temp)
                i++;
            A[j]=A[i];  
        }  
         A[i]=temp;  
        s=i;  
   
     
        if(s==k)  
            return A[k];  
        if(s>k){i=beg;j--;} 
        if(s<k){j=end;i++;}   
    }  
} 

int PriNum(int n)
{
    int i,m;
    m=0;
    for(i=2;i<=sqrt(n);i++)
    {
        if (n%i==0)
        {
            m=1;
            break;
        }
    }
    return m;
}

int main(void) { 
	int n,k,m,min,max,A[10000];
	int i;
	scanf("%d %d",&n,&k);
	for (i=0; i<n; i++)
	    scanf("%d",&A[i]);
	min=MinK(A,n,k-1);
	max=MinK(A,n,n-k);
	printf("%d %d\n",min,max);
	m=max-min;
	if (PriNum(m))
	    printf("No\n%d",m);
	else
	    printf("Yes\n%d",m);
	return 0;
}

© 著作权归作者所有

Anemax
粉丝 0
博文 1
码字总数 196
作品 0
南京
私信 提问
12.1 省选训练总结2(1) 点分治/平衡树

目录 点分治 Splay 完成情况截图 聪聪可可 普通平衡树 文艺平衡树 宠物收养所 Cards Sorting 点分治 首先找重心,然后对过了重心的路径计算,最后递归点分。 前4道题是点分裸题,就不赘述。 ...

OwenOwl
2017/12/01
0
0
BZOJ 3224 Tyvj 1728 普通平衡树

Description 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 1. 插入 数 2. 删除 数(若有多个相同的数,因只删除一个) 3. 查询 数的排名(若有多个相同的数,...

wang3312362136
2018/01/01
0
0
12.2 省选训练总结2(2) LCT/可持久化

目录 LCT 可持久化数据结构 LCT Splay对LCT就好像线段树对链剖。LCT是动态的! Access操作,最重要的操作:把某点到根路径上的所有边设为Prefered Path,也就是挼(rua)到同一个Splay里面,而...

OwenOwl
2017/12/02
0
0
使用k-近邻算法改进约会网站的配对效果。

在上一文中:初识K-近邻算法。已经介绍了kNN(k-近邻算法)的工作原理和代码实现,这次将讲述《机器学习实战》中的一个案例,使用kNN算法来改进越会网站的配对效果。 案例的描述及kNN流程。 ...

Leafage_M
2017/12/19
0
0
找出无序数组中最小的k个数(top k问题)

给定一个无序的整型数组arr,找到其中最小的k个数 该题是互联网面试中十分高频的一道题,如果用普通的排序算法,排序之后自然可以得到最小的k个数,但时间复杂度高达O(NlogN),且普通的排序算...

群星纪元
04/22
3
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周四乱弹 —— 当你简历注水但还是找到了工作

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @花间小酌 :#今日歌曲推荐# 分享成龙的单曲《男儿当自强》。 《男儿当自强》- 成龙 手机党少年们想听歌,请使劲儿戳(这里) @hxg2016 :刚在...

小小编辑
今天
2.7K
22
靠写代码赚钱的一些门路

作者 @mezod 译者 @josephchang10 如今,通过自己的代码去赚钱变得越来越简单,不过对很多人来说依然还是很难,因为他们不知道有哪些门路。 今天给大家分享一个精彩的 GitHub 库,这个库整理...

高级农民工
昨天
4
0
用好项目管理工具,人人都可以成为项目经理

现在市面上的项目管理工具越来越多了,但是大多数都是一些协同工具或轻量项目管理工具。如果是多团队、跨部门使用或者企业级的项目管理,从管理思想到工具运用,需要适应企业的业务流程体系,...

cs平台
昨天
12
0
只需一步,在Spring Boot中统一Restful API返回值格式与统一处理异常

统一返回值 在前后端分离大行其道的今天,有一个统一的返回值格式不仅能使我们的接口看起来更漂亮,而且还可以使前端可以统一处理很多东西,避免很多问题的产生。 比较通用的返回值格式如下:...

晓月寒丶
昨天
69
0
区块链应用到供应链上的好处和实际案例

区块链可以解决供应链中的很多问题,例如记录以及追踪产品。那么使用区块链应用到各产品供应链上到底有什么好处?猎头悬赏平台解优人才网小编给大家做个简单的分享: 使用区块链的最突出的优...

猎头悬赏平台
昨天
32
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部