能被15整除的最大整数

叁歲伎倆 2021-12-22 04:37 209阅读 0赞

### 油井问题 ###

成绩: 5 / 折扣: 0.8

题目见教材P41.2-1

1<= 油井数量 <=2 000 000

输入要求：

输入有油井数量行，第 K 行为第 K 油井的坐标 X ,Y 。其中， 0<=X<2^31,0<=Y<2^31 。

输出要求：

输出有一行， N 为主管道最优位置的最小值

解：

其实就是求中位数，X坐标是不要用的，算法书上到处都有，直接贴代码：

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAX 2000002
    long a[MAX];
    
    int partition(long p,long r)
    {
    	long i = p, j = r + 1, x = a[p], temp;
    	while (1)
    	{
    		while (a[++i] < x && i < r);
    		while (a[--j] > x);
    		if (i >= j) break;
    		temp = a[i];
    		a[i] = a[j];
    		a[j] = temp;
    	}
    	a[p] = a[j];
    	a[j] = x;
    	return j;
    }
    
    long random(long p,long r)
    {
    	long temp, i = (rand() % (r + 1 - p)) + p;
    	temp = a[i];
    	a[i] = a[p];      
    	a[p] = temp;
    	return partition(p, r);
    }
    
    long select(long p, long r,long k)
    {
    	long i, j;
    	if(p == r) return a[p];
    	i = random(p,r);
    	j = i - p + 1;    
    	if(k <= j) return select(p,i,k);
    		else return select(i + 1,r,k - j);
    }
     
    int main()
    {
    	long num = 0,temp;
    	while(scanf("%ld,%ld",&temp,&a[num] )!=EOF) num = num + 1;
    	if(num%2 == 0) temp = num/2+1;
    		else temp = num/2+2;
    	printf("%d\n",select(0,num,temp));
    	system("pause");
    	return 0;
    }

转载于:https://www.cnblogs.com/kiwi/archive/2012/03/22/2412329.html

发表评论取消回复

表情：

评论列表（有 0 条评论，209人围观）

还没有评论，来说两句吧...

相关阅读

相关 JavaScript编程：判断整数是否能被另一个整数整除

在JavaScript中，我们经常需要判断一个整数是否能被另一个整数整除。这在许多应用中都是很常见的需求，例如校验输入的合法性、数据筛选和逻辑控制。本文将介绍几种判断整数是否能

Love The Way You Lie/ 2023年10月16日 12:27/ 0 赞/ 15 阅读

相关容斥原理 AcWing 890. 能被整除的数

容斥原理 AcWing 890. 能被整除的数原题链接 [AcWing 890. 能被整除的数][AcWing 890.] 算法标签容斥原理思路

╰半夏微凉°/ 2023年09月28日 13:24/ 0 赞/ 110 阅读

相关 leetcode 368. 最大整除子集

思路：其实和最长上升子序列的思路基本一致。 dp\[i\]表示以nums\[i\]结尾的最大的整数子集。dp\[i\]=max(dp\[j\]+1,dp\[i\]) 其中nu

雨点打透心脏的1/2处/ 2023年07月03日 08:16/ 0 赞/ 8 阅读

相关判断一个大整数各位的数字之和能否被3整除

字符串存储大整数 include <stdio.h> include <string.h> include <stdlib.h> defi

亦凉/ 2022年12月11日 13:37/ 0 赞/ 261 阅读

相关求【n以内】【能被3或5整除】的整数的【阶乘】【之和】Python

def proA(n): if n == 1: return 1 else: retur

水深无声/ 2022年12月05日 09:53/ 0 赞/ 239 阅读

相关 C语言重构【1262】可被三整除的最大和

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

亦凉/ 2022年11月06日 07:56/ 0 赞/ 179 阅读

相关 368. 最大整除子集

> 给你一个由无重复正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer\[i\], answer\[j\])

向右看齐/ 2022年10月09日 12:15/ 0 赞/ 148 阅读

相关求1～100之间的能被三整除，同时不能被5整除的和

package p1; import java.util.Scanner; /\\ auther:xiuran-hua function:

Dear 丶/ 2022年04月22日 10:00/ 0 赞/ 241 阅读

相关能被15整除的最大整数

油井问题成绩: 5 / 折扣: 0.8 题目见教材P41.2-1 1<= 油井数量 <=2 000 000 输入要求：输入有油井数量行，第 K 行为第 K 油

叁歲伎倆/ 2021年12月22日 04:37/ 0 赞/ 210 阅读

相关判断一个数是否能被另一个整数整除

【题目要求】：判断一个数是否能被另一个整数整除是一个挺简单的问题，一般一个模运算就可以搞定了，懒惰的晓萌还是不想自己做，于是找到你帮他写代码，你就帮帮他吧。【输入格式】：输

阳光穿透心脏的1/2处/ 2021年09月16日 10:34/ 0 赞/ 337 阅读